for-loop - Big-O 和通用时间单位？

Question

我有这两个问题，我认为我理解如何回答（问题后的答案）。我只是想看看我是否理解时间复杂度计算以及如何找到 BigO。
泛型只是表达式右侧每个值的乘积。
BigO 是多项式中的最大幂。这种思维方式正确吗？

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

这段代码需要多少个通用时间单位？n(n^2)*10 这段代码的大运行时间是多少？O(n^3)

score 1 · Accepted Answer

是的。基本上，大 O 的定义表明您的时间单位（正如您所说的那样）从上面受到一个常数时间的限制，您的表达式从某个（任意高）自然数到无穷大。在更数学的符号中，这是：

如果存在一个常数 C 和一个数 N 使得 f(n) < C*g(n) 对于所有 n > N，则函数 f(n) 是 O(g(n))。

在您的上下文中，f(n) = n(n^2)*10 和 g(n) = n^3。

顺便说一句，你也可以说函数是 O(n^4)。您可以使用大 theta 符号来表示这也是下限：f(n) 是 $\theta(n^3)。

score 1 · Accepted Answer

是的，你的理解是正确的。但有时你也必须处理对数项。查看对数项的方法可以将其视为 n^(1+epsilon)。其中 epsilon 是一个小量。

2 回答 2