O(log log N) 复杂度循环是怎样的？

Question

我有一个非常基本的问题

for(int i = 1; i < N/2; i++) {

}

我最初的理解是上述循环的时间复杂度为 O(logn)，但在阅读了一些文章后，很明显它只是 O(n) 和 O(logn) 看起来像 for (i = 1; i <= n; i *= 2)

现在我的问题是 O(log log N) 循环是什么样子的？

Answer 1

那个循环看起来不像 O(log N)。就是这样，一个 O(N/2) 循环。引用定义：

函数 f(x) 被称为 O(g(x)) 当且仅当存在正实数 c 和实数 x0 使得 |f(x)| <= c|g(x)|对于所有 x >= x0。例如，您还可以将该循环称为 O(N)、O(N^2)、O(N^3)，因为您可以轻松找到所需的参数。但是，您找不到使 O(log N) 适合的参数。

至于 O(log log N)，我想您可以重写此处给出的插值搜索实现 https://en.wikipedia.org/wiki/Interpolation_search 以使用 for 循环。平均为 O(log log N)！

Answer 2

O(log n)循环：

for (i = 1; i <= n; i *= 2)

所以你在每一步加倍 i。基本上：

乘法之后是什么？求幂。所以这将是 O(log log n):

for (i = 2; i <= n; i *= i) // we are squaring i at each step

注意： 你的循环是 O(n)，而不是 O(log n)。与上面的 increment / double / exponentiate 想法保持一致，您可以使用增量重写循环：

for(int i = 1; i < n; i += 2)

即使再增加，也是增加，还是O(n).

Answer 3

你的成本不是 O(logN) 你的成本是 O(N*logN)。

阅读 link 您将看到一个函数示例，例如：

无论多项式开头的数是最大的多项式成本。

你的情况是

1/2 * n * log(n) ，其中 1/2 没有区别你的复杂度是 O(N*logN)

How does O(log log N) complexity loop look like?