リンクされたリストで重複を見つけるアルゴリズムを書きました。
ノードごとに、リストの先頭から現在のノードまで繰り返します。重複している場合は削除されます。
私のアルゴリズムの複雑さは何ですか?
リンクされたリストで重複を見つけるアルゴリズムを書きました。
ノードごとに、リストの先頭から現在のノードまで繰り返します。重複している場合は削除されます。
私のアルゴリズムの複雑さは何ですか?
アルゴリズムの複雑さはΘ(n^2)
最悪の場合です。重複がない場合、ノードごとに直線的に増加する回数を反復し、1 + 2 + .... + n
総読み取りの合計がΘ(n^2)
(算術数列の合計から)になるためです。
最良の場合の複雑さはΘ(n)
- すべての要素が重複している場合Θ(n)
複雑さはΘ(n)