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 输出:True

有什么办法可以在 O(n) 时间内完成它吗？如果是，怎么办？

Answer 1

不可能比 O(n) 更好。

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

因此，你至少有 O(n)。