-3

リンクされたリストで重複を見つけるアルゴリズムを書きました。
ノードごとに、リストの先頭から現在のノードまで繰り返します。重複している場合は削除されます。

私のアルゴリズムの複雑さは何ですか?

4

1 に答える 1

4

アルゴリズムの複雑さはΘ(n^2) 最悪の場合です。重複がない場合、ノードごとに直線的に増加する回数を反復し、1 + 2 + .... + n総読み取りの合計がΘ(n^2)(算術数列の合計から)になるためです。


最良の場合の複雑さはΘ(n)- すべての要素が重複している場合Θ(n)複雑さはΘ(n)

于 2012-12-17T10:33:34.967 に答える