LinkedList和BinarySearch的大O表示法[重复]

Question

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

从此以后的第三行()，

list.get( middle )

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

我猜如果将ArrayList传递给函数，它会给你更好的性能。试试看。很好，您使用List泛型接口实现了函数，您应该能够传递ArrayList。