c++ - 以大 O 表示法查找运行时间

Question

1)  for (i = 1; i < n; i++) {                         > n
2)      SmallPos = i;                                 > n-1
3)      Smallest = Array[SmallPos];                   > n-1
4)      for (j = i+1; j <= n; j++)                    >  n*(n+1 -i-1)??
5)          if (Array[j] < Smallest) {                > n*(n+1 -i-1 +1)  ?? 
6)              SmallPos = j;                         > n*(n+1 -i-1 +1)  ?? 
7)              Smallest  = Array[SmallPos]           > n*(n+1 -i-1 +1)  ??     
            }                                         
8)      Array[SmallPos] = Array[i];                   > n-1
   9)                Array[i] = Smallest;             > n-1
                                     }

我知道大 O 符号是 n^2(我的错不是 n^3)

我不确定第 4-7 行之间有人愿意帮忙吗？我不确定如何获得第二个循环的输出，因为 j = i +1 随着 i 的变化，j 也是如此

同样对于第 4 行，ans 假设为 n(n+1)/2 -1 我想知道为什么我永远无法得到它

我并没有真正解决大 O 我正在尝试执行将大 O 作为常量和变量排除在大 O 符号中的步骤。

Answer 1

我会说这是 O(n^2)(尽管正如 Fred 在上面指出的那样，O(n^2) 是 O(n^3) 的子集，所以说它是 O(n ^3)).

请注意，通常没有必要计算每一行 的执行次数；由于 Big-O 符号会丢弃低阶项，因此仅关注执行次数最多的部分(通常位于最内层循环内)就足够了。

因此在您的情况下，没有任何循环会受到 Array 中的值的影响，因此我们可以安全地忽略所有这些。最里面的循环运行 (n-1) + (n-2) + (n-3) + ... 次；这是一个arithmetic series , 因此在 n^2 中有一个项。