両方の操作の時間計算量はO（log n）に等しいですか？覚えておいてください：リストは順序付けられており、常に順序付けられており、二重にリンクされていません。
1100 次
1 に答える
8
順序付けられたリンクリストでの挿入と削除はどちらもO(n)-最初に削除/追加したいものを見つける必要があるため[削除では関連するノードを見つけ、挿入では-その正しい場所を見つける]-これはO(n)-たとえ頭から繰り返しながらこの場所にたどり着く必要があるため、リストが並べ替えられます。
迅速な挿入、削除、検索を可能にする効率的な特殊なタイプのリストはスキップリストと呼ばれ、隣接していないノード間ですばやく反復するために、より多くのノードを使用します。
于 2012-04-18T21:54:30.930 に答える