如何在小于 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 输出：假

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

有没有什么办法可以在小于 O(n) 的时间内做到这一点？如果是，如何？

Answer 1

不可能以比 O(n) 更好的方式做到这一点。

每个元素都可以有一个值，将解决方案从 true 更改为 false。所以，你至少需要对每个元素做一个操作，来检查它。

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

Answer 2

显然，您需要 O(N) 遍历才能产生true.

您可以进行的优化是尽快产生一个false。

我推测（并认为证明会很困难，但如果数字是算术分布的，则证明是正确的）相邻的较大数字对（a，b）比较小的数字更不可能是整数n的形式（a，na）。因此，您可以通过首先考虑较大的数字来更快地产生。换句话说，从最后一个元素到第一个元素运行循环很可能最终会在统计上更快。您必须对呈现给您的函数的典型数字系列进行概要分析。false

顺便说一下，你的序言

if (no_of_elements == 1)
    return true;

是多余的。