リストにはハッシュ可能なオブジェクトのみが含まれていると想定します。
ところで、私は複雑さや学術的なことに関しては完全な初心者なので、この質問が理にかなっているかどうかはわかりません。
質問する
3144 次
2 に答える
20
2つのリストを比較する複雑さは、両方のリストの長さがnの場合はO（n）であり、リストの長さが異なる場合はO（1）です。
于 2012-07-03T15:15:44.893 に答える
5
これは、「比較」という言葉の意味に大きく依存します。
等しいかどうかを比較すると、@ Sven-Marnachの答えが当てはまります。同じ長さの場合はO（n）、異なる長さの場合はO（1）です。
ハッシュ関数を使用すると、多くのリストを相互に比較する場合に役立ちます。ハッシュ値が異なる可能性があるため、異なるリスト（異なるハッシュ）の場合はO（1）であり、同じハッシュのリストの場合はO（n）である可能性があります。衝突し、実際の比較を行う必要があります。これは、複数のハッシュ関数を使用することで軽減できるため、衝突の可能性が大幅に減少します。
長さnのリストのハッシュ値を計算するにはまだO（n）が必要であるため、ここでは無料の昼食はありません。
2つのリストの類似性を比較する場合は、単純なケースでは時間的に2次であるが、遅延評価によって線形にすることができるレーベンシュタイン距離が必要になります。これは、おそらくメモリを大量に消費します。
あるリストを別のリストから作成するために行う変更の完全なリストを計算する場合（diff）、ウィキペディアに記載されている最良の実装では2次式です。
于 2012-07-03T15:33:51.403 に答える