Big O 运行时 - indexOf LinkedList/ ArrayList

Question

我有一个关于 Big O 运行时和 LinkedList 和 ArrayList 中的 indexOf 方法的问题。我如何提出 Big O 运行时假设以及它在链表和数组列表中有何不同？

LinkedList indexOf()

public int indexOf(Object value)
{
    int results = -1;
    boolean done = false;
    Node<E> ref = head.next;
    for(int i = 0; i < size && !done; i++)
    {
        if(value.equals(ref.value))
        {
            results = i;
            done = true;
        }
        ref = ref.next;
    }
    return results;
}

ArrayList indexOf()

if (o == null) {
            for (int i = 0; i < size; i++)
                if (Values[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(Values[i]))
                    return i;
        }
        return -1;

如果这对某些人来说是一个微不足道的问题，我深表歉意，但我需要了解如何提出方法的 Big O 运行时。

Answer 1

在这两种实现中，您没有什么比一次遍历列表中的一个元素并将其与您要查找的值进行比较更好的事情了。在最坏的情况下，您将遍历整个列表，复杂度为 O(n)。