algorithm - asymptotic-complexity - 计算原始操作的步骤

Question

我在理解应该如何计算以下算法的原始操作时遇到了一些困难。

我知道步骤的计算是这样的:

(1) = 1 步:赋值

(2) = 1 步:赋值

(3) = 3+(n-1) 步:3 次比较，进行 (n-1) 次

(4) = 1 步:赋值

(5) = 2+(n-2): 赋值比较，进行(n-1)+(n-2)+...+2+1=(n-1)n/2次

(6) = 3 个步骤:两个数组，一个比较 [<] 和一个操作 [-]

(7) = 4 步:两个数组，一个操作 [-] 和函数调用交换，这是第 3 步 n(1)

(8) = 2步:赋值和加法运算

我可以推断出最坏的情况是 (n^2+n+2n+2) = O(n^2) 因为最坏的情况是列表以第一个值作为大值排序并且作为最小值的最后一个值是 i=0 到 n (i-1) 的总和。

也是列表已经排序的最佳情况，这意味着列表将以恒定速度运行。

我的问题是找到如何从算法中收集原始操作，这样我就可以通过计算 c 和 n_0 自己用 Ordo 的定义来证明这一点。

Answer 1

当有人说排序算法具有特定的时间复杂度时，他们通常指的是所需的比较次数。正如您已经完成的那样，您需要计算元素之间的比较次数并计算出常量。