计算大 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 循环中可能会执行交换操作。
• 交换( A[i-1]， A[i] ) 每个都会发生 n^2 次。
• 因此在 j 循环中执行了 2n^2 个操作
i
• 循环有一个递增 i 的加法运算，发生在 n 次
• 将这些相加，我们得到加法运算的数量，即 2n^2 + n
• 当 n 变得非常大时，n^2 将占主导地位，因此它是 O(n^2)

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

标记概述：

• 用于识别 i 循环的 1 个标记将执行 n 次。
• 用于识别 j 循环的 1 个标记将执行 2n^2 次这不是意味着 n*n = n^2 吗？对于 i 和 j
• 1 标记表示正确的计算次数 2n^2 + n为什么不是 +2n？
• 1 标记，用于确定订单将由 n^2 主导为 n 为算法提供 O(n^2) 非常大

编辑：从标记方案中可以看出，我应该计算：

• 循环号，但 n-1 可以截断为 n
• 比较，例如 if 语句
• 数据交换(计为一个语句，即 arr[i] = arr[i+1]，temp = arr[i]，等等被视为一个交换)
• 计算
• 空格 - 只有 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