C# Liste supprimer de la fin, vraiment O(n)?

La suppression du dernier élément sera effectivement O(1) opération depuis seulement dans ce cas List ne passe pas à côté d'éléments dans le tableau. Voici un code de Réflecteur:

this._size--;
if (index < this._size) //this statement is false if index equals last index in List
{
    Array.Copy(this._items, index + 1, this._items, index, this._size - index);
}
this._items[this._size] = default(T);

Lorsque l'on parle asymptotiquement, O(N) est le pire des cas le temps de la complexité de la méthode elle-même, où N est le nombre de. Il ne peut pas effectuer de pire que cela.

En pratique, il serait de l'ordre de O(N-I) (sans tenir compte de la constante de temps système), où I est l'indice. Ce ressort, puisque tous les éléments au-delà de l'index j'ai besoin d'être déplacé à la position précédente respectivement dans une Liste.

De voir cela intuitivement, si N est de 100 et de l'indice est de 99 (dernier élément), alors il n'y a pas d'éléments qui doivent être "décalé" juste le dernier élément est supprimé (ou tout simplement le nombre est diminué, sans modification de la taille de la structure de données).

De même, lorsque N est de 100, l'indice est 0 (premier élément), 99 changements doivent être faits.

Exécutez le code suivant et de voir par vous-même:

int size = 1000000;
var list1 = new List<int>();
var list2 = new List<int>();

for (int i = 0; i < size; i++)
{
    list1.Add(i);
    list2.Add(i);
}

var sw = Stopwatch.StartNew();
for (int i = 0; i < size; i++)
{
    list1.RemoveAt(size-1);
    list1.Add(0);
}
sw.Stop();
Console.WriteLine("Time elapsed: {0}", sw.ElapsedMilliseconds);

sw = Stopwatch.StartNew();
for (int i = 0; i < size; i++)
{
    list2.RemoveAt(0);
    list2.Add(0);
}
sw.Stop();

Console.WriteLine("Time elapsed: {0}", sw.ElapsedMilliseconds);