LinkedList和BinarySearch的Big-O表示法

Question

我正在尝试计算此代码的Big Oh，它用于在链表上执行二进制搜索：

public int search( List<T> list, T target ) {
        int low = 0;
        int high = list.size() - 1;
        int middle;
        while ( low <= high ) {             // frequency << log( n )
            middle = ( low + high ) / 2;
            int cmp = target.compareTo( list.get( middle ) );   // time << n
            if ( cmp < 0 ) high = middle - 1;
            else if ( cmp > 0 ) low = middle + 1;
            else return middle;
        }   // time << n log( n )
        return -1;
}   // time << n log( n )

我得到O（n log（n））作为答案。这是计算这种类型列表的搜索方法的正确方法吗？

Answer 1

while（）的第三行，

list.get( middle )

对于linkedList来说是昂贵的，它是O（n/2）平均情况==O（n），但对于arrayList来说是O（1），所以即使算法缩小到O（logn）中的一个元素，访问每个循环中的数组元素也会导致O（n。

我猜，如果您将ArrayList传递给函数，它会给您带来更好的性能。试试看。如果您使用List通用接口实现了函数，那么您应该能够传递ArrayList。

确保你研究了arraylist和linkedlist在访问/索引、读取、写入、搜索、克隆操作方面的区别。。。等等