ios - NSMutableArray でのオブジェクトの追加と削除の複雑さは何ですか?

Question

オブジェクトを追加するには、より大きなサイズの新しい配列を作成 + 古い配列のコピーを作成 + 要素を追加する必要があると思います。したがって、最終的な複雑さは O(N) です。ここで、N - 最終的な要素数です。

削除 - O(N) も。

私が間違っている？

どうも。

Answer 1

I think that to add an object we need: create new array with a bigger size + make a copy of older array + add an element.

いやぁぁぁぁぁぁぁ....

オブジェクトを追加するために、新しい配列は作成されず、それらすべてが行われます。

ココアにはすべてのポインターがあることを覚えている場合。また、C/C++ にポインターが含まれている場合は、それをリンクされたリストと見なしてください。新しい要素を追加するには、そのアドレスのみがリストに保存され、必要に応じてヘッド/テールが調整されます。

MutableArrays の場合も同じです。

複雑さは O(1) である必要があります。