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

m0からまでの範囲である必要があります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

私はおそらくこれを少し冗長にしています。