算法大o阶增长代码

Question

我正在上在线课程，但我被这个问题困住了。我知道有类似的问题，但他们对我没有帮助。

What is the order of growth of the worst case running time of the following code fragment as a function of N?

int sum = 0;
for (int i = 0; i*i*i < N; i++)
    for (int j = 0; j*j*j < N; j++)
        for (int k = 0; k*k*k < N; k++)
            sum++;

我认为顺序应该是 n^3，但我认为这是不正确的，因为循环每次只经过 n 的三分之一。那会使它变成 nlogn 吗？

还有

int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
        for (int k = 1; k <= N; k = k*2)
            for (int h = 1; h <= k; h++)
                sum++;

我想这个应该是 n^4 因为你有 n * n * 0.5n * 0.5n

Answer 1

实际上循环只达到 N 的立方根。（i^3 < n，等等）

这个长度的3个嵌套循环，给出O（N的立方根，立方）。这个 O(N)

值得注意的是，如果你是对的，他们每个人都去了 N 的三分之一，那么立方这仍然是 O(N^3/9)，1/9 是常数，所以这是 O(n^3 )

Answer 2

如果您针对 N 的各种值检查 sum 的值，那么算法的时间复杂度是多少就很清楚了：

#include <iostream>

int main()
{
  for( int N=1 ; N<=100 ; ++N ) {
    int sum = 0;
    for (int i = 0; i*i*i < N; i++)
      for (int j = 0; j*j*j < N; j++)
        for (int k = 0; k*k*k < N; k++)
          sum++;
    std::cout << "For N=" << N << ", sum=" << sum << '\n';
  }
  return 0;
}

然后您可以更深入地得出自己的结论。

算法大o阶增长代码

Algorithmic big o order of growth code

algorithm

discrete-mathematics