TimeComplexityのドキュメントに見られるように、Python のlist型は配列を使用して実装されています。
したがって、配列が使用されていて、いくつかの追加を行う場合、最終的にスペースを再割り当てし、すべての情報を新しいスペースにコピーする必要があります。
結局のところ、どうすれば O(1) 最悪のケースになるのでしょうか?
質問する
68655 次
3 に答える
85
O(1) ではなく、O(1) に償却されます。
リストの予約サイズが 8 要素で、スペースがなくなるとサイズが 2 倍になるとします。50 個の要素をプッシュしたいとします。
最初の 8 つの要素は O(1) をプッシュします。9 番目は、再割り当てと 8 つのコピーをトリガーし、その後に O(1) プッシュを行います。O(1) の次の 7 プッシュ。17 番目は、再割り当てと 16 個のコピーをトリガーし、その後に O(1) プッシュが続きます。O(1) の次の 15 プッシュ。33 番目は再割り当てと 32 個のコピーをトリガーし、その後に O(1) プッシュが続きます。O(1) での次の 17 回のプッシュ。
したがって、すべてのプッシュは O(1) の複雑さを持ち、O(1) で 56 個のコピーがあり、O(n) で n = 8、16、および 32 の 3 つの再割り当てがありました。これは等比級数であり、漸近的であることに注意してください。 O(n) に等しく、n = リストの最終サイズです。つまり、n 個のオブジェクトをリストにプッシュする操作全体は O(n) です。それを要素ごとに償却すると、O(n)/n = O(1) になります。
于 2015-10-09T18:34:39.313 に答える
40
リンクしたドキュメントの脚注を見ると、警告が含まれていることがわかります。
これらの操作は、「償却された最悪のケース」の「償却された」部分に依存しています。コンテナーの履歴によっては、個々のアクションに驚くほど時間がかかる場合があります。
償却分析を使用すると、時折高価な操作を実行する必要がある場合でも、それらを個別ではなく一連の操作と見なすと、操作の「平均」コストの下限を得ることができます。
したがって、個々の操作は非常に高価になる可能性があります - O(n) または O(n^2) またはそれ以上のもの - しかし、これらの操作はまれであることを知っているので、O(n) 操作のシーケンスを次のように実行できることを保証します定刻。
于 2015-10-09T18:27:02.440 に答える