algorithm - 执行 nm 操作的算法的大 O 是多少，其中 m 是迭代次数？

Question

我写了一个算法来查找未排序列表中的重复项。它在每次迭代中执行 n - m 次操作，其中 m 是迭代次数，n 是输入列表的大小。它的大O是多少？

Answer 1

O(n^2)。这里的工作是n+(n-1)+(n-2)+...+1 = n(n+1)/2。

一种更直观的看待它的方式是，您至少n/2为至少n/2迭代工作，所以您至少n^2/4工作。

Answer 2

  (n - m) + (n - m - 1) + (n - m - 2) + ... + (n - m - m)
= (n * m) + m + (m - 1) + (m - 2) .. - (m - m)     # Group the `n`s
= (n * m) + (1 + 2 + .. + m)                       # Carefully reverse this sum
= (n * m) + 0.5 * m * (m + 1)                      # sum(1...n) = n(n+1)/2

m范围应为0至n，因此：

= (n * n) + 0.5 * n * n + 0.5 * n                  # Just substitute `n` for `m`
= 3/2 * n^2 + 0.5 * n                              # Combine the `n^2` terms
-> 3/2 * n^2                                       # n^2 >> n for large enough n
=> n^2                                             # Drop the constant

我可能这样做有点过于冗长了。