big-o - 我的算法的大 O 是多少？

Question

我需要帮助来找到这个算法的重要之处。这是一种搜索算法，它正在划分和征服我的大小为 n 的数组以找到第一次出现的 false，a 是一个数组。

n=a.length;
i=0;
while(a[i]){
   i += n/2;
   n=n/2;
}
       i -= n;
while(a[i])
   i++;

//希望，我会在第一次出现错误时停止。

Answer 1

第一部分：

n=a.length;
i=0;
while(a[i]){
   i += n/2;
   n=n/2;
}

在 O(lg N) 中执行：i = (nn), (nn/2), (nn/4), ...

但它可能有问题。让我们假设 N=63。然后：

i = 0   and n = 63, so n/2 is 31.5, and being an integer, it is 31.
i = 31  and n = 31, so n/2 is ... 15
i = 46  and n = 15, so n/2 is ... 7
i = 53  and n = 7, so n/2 ... 3
i = 56  and n = 3, so n/2 ... 1
i = 57  and n = 1, so n/2 = 0

现在 if a[57]istrue循环将永远不会结束，因为将 n=0 添加到最终索引将使其保持不变。

如果您以某个非零值退出循环n，则您处于n/k某个 k 值，并开始递增 i。

i -= n;
while(a[i])
   i++;

在这里，您增加n/k了复杂性，最坏情况下为 O(N)，最好情况下为 O(1)，但在这两种情况下，一旦i超出数组边界，您就会访问非法内存，并且可能是 coredump。你应该做类似的事情

i -= n;
while((i < n) && (a[i]))
   i++;

否则，您的算法可能介于 O(lg N) 和 O(N) 之间，但它可能永远不会终止或异常终止。

Answer 2

如果您正在搜索仅包含布尔真/假值的数组，那么这些值无法以任何允许您描述的二进制搜索的方式排序。如果数组包含一个排序的值列表，那么您将能够使用 O(log n) 的二进制搜索的分而治之。要找到第一次出现的错误，您需要检查数组的每个值，最坏的情况是 O(n)。

int i = 0;
for (i; i < a.length; i++) {
    if (a[i] == false){
        break;
    }

}
return i;