プライオリティ キューを実装しており、リストを反復処理して適切な場所に挿入したいと考えています。ドキュメントでは、C#List<T>.Itemプロパティは O(1):
List<T>.Itemプロパティであると記載されています。
例えば
int retrivedValue = myIntList[5];
add も O(1) であるため、これはどのように可能ですか? クッキーを食べてまだ持っているようなものです。私の頭の中の通常のリストには、要素にアクセスするための O(n) があります。
はList<T>配列によって支えられています。
Add操作は、すべての add で償却されるO(1) です。つまり、ほとんどの操作は O(1) ですが、一部は O(N) です。バッキング配列がいっぱいになるたびに、2 倍のサイズの新しい配列にコピーされます。
どのように機能するかの例として、バッキング配列が 4 つの要素で始まるとします。最初の 4 つの追加は O(1) ですが、5 つ目は既存の 4 つの要素をコピーして 5 つ目を追加し、O(5) にする必要があります。要素 6、7、および 8 を追加すると O(1) になりますが、要素 9 を追加すると O(9) になります。次に、要素 10 ～ 16 も O(1) になります。
配列に 16 個の要素を追加するまでに、O(28) 回の操作を行ったことになるため、N 個の要素を追加するにはほぼ O(2N) 回の操作が必要になります。したがって、単一の要素を追加すると、平均で O(2) = O(1) になります。
リストは内部的に配列を使用するため、インデックス付けは直接操作です。また、最後に追加するのは高速です（再割り当てが必要でない限り）。ただし、配列のすべての要素を移動する必要があるため、挿入と削除は O(n) です。実際には、移動は配列の右側部分の単一のブロック移動として実装されるため、これもそれほど悪くはありません。
