algorithm - 为什么 ArrayList 在 O(n) 而不是 O(n*n) 中删除功能

Question

请问下面Remove函数的时间复杂度是O(n)还是O(n*n)？

它删除集合中第一个值与提供的值匹配的项，如果删除了一个值，则返回 true。否则返回 false。

public bool Remove(T item) 
{ 
    for (int i = 0; i < Count; i++) 
    {
       if (_items[i].Equals(item)) 
       {
         RemoveAt(i); 
         return true; 
       }
    } 
    return false; 
}

public void RemoveAt(int index)
{
    if (index >= Count)
    {
        throw new Exception("Index out of Range");
    }

    var sourceIndex = index + 1;
    Array.Copy(_array, sourceIndex, _array, index, _array.Length - sourceIndex);

    Count--;
}

Answer 1

public bool Remove(T item) 
{ 
    for (int i = 0; i < Count; i++) // say count = n. this loop will run n times.
    {
       if (_items[i].Equals(item)) // say if operation takes 10 units of time
       {
         RemoveAt(i);  
         return true;  // say this operation takes 2 units of time
       }
    } 
    return false; // say this operation takes 2 units of time
}

public void RemoveAt(int index) {
    if (index >= Count) // say this operation takes 10 units of time
    {
        throw new Exception("Index out of Range"); // say this operation takes 4 units of time
    }

    var sourceIndex = index + 1; // say this operation takes 2 units of time
    Array.Copy(_array, sourceIndex, _array, index, _array.Length - sourceIndex); // say this operation takes 10 units of time

    Count--; // say this operation takes 5 units of time
}

这意味着 RemoveAt 需要 10 + 4 + 2 + 10 + 5 个时间单位 = 31 个时间单位 而 Remove 需要 n * (10 + 31 + 2) 个时间单位 = n * 43 个时间单位。

任何需要固定时间量的操作都称为 O(1) 操作。因此，Remove 需要 n * O(1) 时间单位，其数量级为 O(n)