Big-O & Big-Theta：for 循环是 O(1) 时间复杂度吗？

Question

我很难理解 Big-O 和 Big-Theta 的确切含义。有人可以解释一下它的含义吗？

假设n为常数，那么最坏情况下的for循环是O(1)时间复杂度吗？

此外，由于插入排序的复杂度为 O(n^2)，所以算法的最坏情况运行时间是否低于 O(n^2)？如果不是，下面算法在最坏情况下的时间复杂度是多少？

void fnA(int[] array)
{
   ArrayList a2 = new ArrayList<Integer>(array.length);

   for (int i=0; i<n; i++) {
      a2.add(array[i]);
      insertionSort(a2);
   }
}

Answer 1

你可以认为Big-O是上界。如果你有一个for循环。说

for i:= 1 to 10 print("hello");

那么它的复杂度是O(1)。 O(1) 并不意味着它在 1 条指令中完成。它只是意味着它不会随着输入大小（即 n）的运行时间而变化。同样，O(n) 意味着它的运行时间与输入大小成正比。

对于您的示例，您可以通过这样思考使其变得简单：您有一个复杂度为 O(n) 的外部 for 循环。然后在循环体内，调用 add（O(1)）和 insertionSort（O(n^2)）。那么总的复杂度是 O(n) * (max(O(1), O(n^2)) = O(n^3).

实际上它只是估计复杂度的一种快速方法。为了更准确的方法，你应该做一些数学运算，比如当a2的长度为1,2,3。...，n时，插入排序需要执行多少条指令。然后总结一下。它会给你一些公式，其中最重要的一项是 n^3.

Big-O & Big-Theta：for 循环是 O(1) 时间复杂度吗？

Big-O & Big-Theta: is a for loop O(1) time complexity?

for-loop

big-o

time-complexity

big-theta