在O(logn)时间内找到最大值？

Question

我一直认为迭代搜索是在未排序列表中查找最大值的首选方法.

这个想法相当随机,但简而言之:我相信我可以在O(logn)时间内完成任务,n是输入数组的大小.

合并排序的方法:分而治之.

步骤1:将findMax()任务划分为两个子任务findMax(leftHalf)和findMax(rightHalf).这个部门应该及时完成O(logn).

第2步:合并两个最大候选人备份.该步骤中的每个层应该花费恒定的时间O(1),并且在前一步骤中存在O(logn)这样的层.所以它也应该及时完成O(1) * O(logn) = O(logn)(原谅滥用符号).这是错的.每次比较都是在恒定时间内完成的,但是还有2^j/2这样的比较(第j级的2 ^ j对候选者).

因此,整个任务应该及时完成O(logn). O(n)时间.

但是,当我尝试计时时,我会得到清晰反映线性O(n)运行时间的结果.

size = 100000000 max = 0 time = 556

size = 200000000 max = 0 time = 1087

size = 300000000 max = 0 time = 1648

size = 400000000 max = 0 time = 1990

size = 500000000 max = 0 time = 2190

size = 600000000 max = 0 time = 2788

size = 700000000 max = 0 time = 3586

怎么会？

这是代码(我保留未初始化的数组以节省预处理时间,该方法,据我测试它,准确识别未排序数组中的最大值):

public static short findMax(short[] list) {
    return findMax(list, 0, list.length);
}

public static short findMax(short[] list, int start, int end) {
    if(end - start == 1) {
        return list[start];
    }
    else {
        short leftMax = findMax(list, start, start+(end-start)/2);
        short rightMax = findMax(list, start+(end-start)/2, end);
        return (leftMax <= rightMax) ? (rightMax) : (leftMax);
    }
}

public static void main(String[] args) {
    for(int j=1; j < 10; j++) { 
        int size = j*100000000; // 100mil to 900mil
        short[] x = new short[size];
        long start = System.currentTimeMillis();
        int max = findMax(x);
        long end = System.currentTimeMillis();
        System.out.println("size = " + size + "\t\t\tmax = " + max + "\t\t\t time = " + (end - start));
        System.out.println();
    }
}

Answer 1

您应该计算实际发生的比较次数:

在最后一步中,在找到前n/2个数和最后n/2个nubmers的最大值后,需要再进行1次比较才能找到整组数的最大值.

在上一步中,您必须找到第一组和第二组n/4数的最大值以及第三组和第四组n/4数的最大值,因此您有2次比较.

最后,在递归结束时,你有n/2组2个数字,你必须比较每一对,所以你有n/2个比较.

当你总结他们所得到的:

1 + 2 + 4 + ... + n/2 = n-1 = O(n)