计算大 O 交换、计算和比较

Question

查看下面的代码：

Algorithm sort

Declare A(1 to n)

n = length(A)

for i = 1 to n
    for j = 1 to n-1 inclusive do
       if A[i-1] > A[i] then
          swap( A[i-1], A[i] )
       end if
  next j
next i

我会说有：

• 2 次循环，均为 n，n*n = n^2（n-1 截断为 n）
• 1次比较，第j次循环，执行n^2次
• 将执行 n^2 次的交换
• 循环中还有2n次加法，执行n^2次，所以2n^2

评分方案给出的答案：

算法评价

比较

唯一的比较出现在 j 循环中。 因为这个循环总共会迭代 n^2 次，它会执行 恰好 n^2

数据交换

• j循环中可能进行了交换操作
• Swap( A[i-1], A[i] ) 每一个都会发生 n^2 次。
• 因此j循环内进行了2n^2次操作
• 第 i 个循环有一个递增 i 的加法运算，它发生在 n 次
• 将这些加起来我们的加法运算次数是 2n^2 + n
• 随着 n 变得非常大，n^2 将占主导地位，因此它是 O(n^2)

注意：计算可能包括赋值操作，但这些不会影响总时间，因此请忽略

标记概述：

• 1个标志标识第i个循环会执行n次
• 1个标识j循环的标记会执行2n^2次这不就是n*n = n^2吗？对于 i 和 j
• 1 分正确的计算次数 2n^2 + n 为什么这不是 +2n?
• 1标记确定顺序将以n^2为n为主 为算法提供 O(n^2) 变得非常大

编辑：从mark scheme可以看出，我预计要数：

• 循环数，但n-1可以截断为n
• 比较，例如如果语句
• 数据交换（计为一次语句，即arr[i] = arr[i+1]、temp = arr[i]等被认为是一次交换）
• 计算
• Space - 仅 n 表示数组等

谁能解释一下这些答案是如何得出的？

谢谢！

Answer 1

这是我对标记方案的看法，明确标记了他们正在计算的操作。他们似乎在计算作业（但很方便地忘记了需要 2 或 3 个作业才能进行交换）。这解释了为什么他们计算增量而不是 [i-1] 索引。

计算交换

i loop runs n times
    j loop runs n-1 times (~n^2-n)
        swap (happens n^2 times)            n^2

计算加法 (+=)

i loop runs n times 
    j loop runs n-1 times (~n^2)
        increment j (happens n^2 times)     n^2
    increment i (happens n times)           n

sum:                                        2n^2 + n