最善のケースと最悪のケースでは、並べ替えられていない配列に挿入するための時間の複雑さ

Question

これは一般的な質問ですが、私は時間の複雑さについて勉強しているので、本当に疑問を解消する必要があります。私はここに掲示する前にそれを調べようとしましたが、混合回答が見つかりました。

私の質問は、未分類の配列に項目を挿入すると、完全ではないとみなして複雑さはO（1）になりますが、フルであればすべての項目を新しい配列。したがって、配列内の挿入の最良の複雑さはO（1）であり、最悪の場合はO（n）か、最善と最悪の場合の両方がO（n）であると言うべきですか？

Answer 1

配列全体を大きな配列にコピーする必要がある場合は、実際には最悪の場合の挿入はO(n)です。しかし、あなたが覚えておかなければならないのは、私たちが気にする償却コストです。

このように考えると、アレイ全体をどのくらいの頻度でコピーする必要がありますか？一度n回。 n-1の場合はO(1)を、最終的にはO(n)とします。 合計で~2nnの挿入。オペレーション当たり平均O(1)。 O(2)と考えるほうが簡単かもしれません。

これを維持するには、配列が塗りつぶされるたびにその2倍のサイズが割り当てられる必要があります。したがって、挿入する各アイテムに対して、最初の半分に対応するアイテムをコピーする必要がある場合は、アレイ。