c++ - 如何在小于 O(N) 的时间内解决这个问题？

Question

我有一个排序（升序）元素的数组作为输入。我想知道这些元素是否构成一个系列，其中每个当前元素都可以被它之前的所有元素整除。这是我能想到的在 O(n) 时间内解决这个问题的明显方法：

bool CheckArray(int arr[], int no_of_elements)
{
    if (no_of_elements == 1)
        return true;

    for (int i = 1; i < no_of_elements; i++)
        if (arr[i] % arr[i - 1] != 0)
            return false;
    return true;
}

示例 1：输入：3 6 9 12 输出：False

示例 2：输入：3 6 12 输出：真

有什么方法可以在少于 O(n) 的时间内完成吗？如果是，如何？

标签： c++time-complexity

Answer 1

不可能比 O(n) 做得更好。

每个元素都可以有一个值，将解决方案从真更改为假。因此，您至少需要对每个元素进行一次操作，以检查它。

因此，您将至少有 O(n)。