二重リンクリスト（O（1））でのノード削除の時間計算量が、単一リンクリスト（O（n））でのノード削除よりも速いのはなぜですか？
質問する
60752 次
8 に答える
6
後ろが見えないから…
于 2009-12-15T03:15:29.127 に答える
4
既知の位置での挿入と削除は O(1) です。ただし、その位置を見つけることは、リストの先頭または末尾でない限り、O(n) です。
挿入と削除の複雑さについて話すときは、通常、それがどこで発生するかを既に知っていると想定しています。
于 2014-11-17T07:51:10.270 に答える
3
これは、削除するノードの前のノードで次のポインターを修正する複雑さと関係があります。
于 2009-12-13T06:53:51.037 に答える
3
削除する要素が先頭 (または最初) のノードでない限り、削除する要素の前のノードにトラバースする必要があります。したがって、最悪の場合、つまり最後のノードを削除する必要がある場合、ポインターは最後から 2 番目のノードまで移動する必要があり、それによって (n-1) の位置をトラバースし、O(n) の時間計算量が得られます。 .
于 2016-08-05T06:40:16.847 に答える