List.Addの漸近的な複雑さは何ですか？

Question

私は、漸近複雑度List.Add()について多くの論争があることを発見しました。私が疑うのは、最悪のシナリオであるthat causes underlying array to resizeであり、論理的にはO(n)の操作になります。ただし、毎回array grows twice in sizeに空き領域がなくなります。これにより、n要素に必要なサイズ変更の量はlog(n)に比例します。

つまり、の平均操作での漸近的な複雑さはO(n/log(n))になりますか？

List.Add()の実際のベンチマークは以下のとおりです。しかし、ベンチマークはそのような操作に実際には表現されていません。ストレート（対数目盛り）からのずれが目に見えるようになる前にメモリが不足している可能性があります。

Answer 1

これは、List.Add()のamortized complexityは、サイズ変更操作を合計して、リストに加えられた総加算の数を掛けることによって算出することができることを意味します。

T(n) = (2 + 4 + 8 + ... + n/2 + n)/n 

しかし

は総和が geometric seriesであることに注意してください、と我々はそれが（合計） n*log(n)だと仮定するとより良く行うことができます。

T(n) < 2n/n = 2 -> T(n) is in O(1) 

---

注：ここで私はあなたが追加としてadd()を意味すると仮定しています。任意の場所に要素を挿入するには、O(n)の時間がかかります。そのためにも同様に考慮する必要があります。O(1)の償却後の複雑さは、償却された複雑さO(n)に変更されます。