Big O runtime - indexOf LinkedList/ ArrayList

Question

我有一个问题，考虑到大O运行时和LinkedList和ArrayList中的indexOf方法。我怎么能提出一个大0运行时假设，它在链表中与数组列表中有什么不同?

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;

我很抱歉，如果这是一个微不足道的问题，但我将需要了解如何提出一个方法的大O运行时

Answer 1

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