如何在C#中实现List <T> .IndexOf()？

Question

我正在考虑打电话的表现List<T>.Indexof(item).我不确定它对于顺序算法的O(n)性能还是二叉树的O(log(n))性能？

Answer 1

使用Reflector for .NET,我们可以看到:

public int IndexOf(T item)
{
    return Array.IndexOf<T>(this._items, item, 0, this._size);
}

public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
{
    return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
}

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
            return i;
    }
    return -1;
}

Answer 2

这是O(n)根据MSDN.

该方法执行线性搜索; 因此,该方法是O(n)操作,其中n是Count.

Answer 3

List<T>由扁平数组支持,list.IndexOf(item)O(n)也是如此.

Answer 4

List<T>.IndexOf 是O(n),实际上对于无序的n个元素集是最优的.

List<T>.BinarySearch 是O(log n)但只有在排序List时才能正常工作.