1

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

这个想法是随机出现的，但简而言之：我相信我可以在 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)运行时间。

大小 = 100000000 最大值 = 0 时间 = 556

大小 = 200000000 最大值 = 0 时间 = 1087

大小 = 300000000 最大值 = 0 时间 = 1648

大小 = 400000000 最大值 = 0 时间 = 1990

大小 = 500000000 最大值 = 0 时间 = 2190

大小 = 600000000 最大值 = 0 时间 = 2788

大小 = 700000000 最大值 = 0 时间 = 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();
    }
}
4

3 回答 3

6

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

在最后一步中，在找到前 n/2 个数字和后 n/2 个数字的最大值后，您需要再进行 1 次比较才能找到整个数字集的最大值。

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

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

当你把它们加起来时，你会得到：

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

于 2013-09-08T13:14:24.080 回答
1

您确实创建log(n)了图层。

但归根结底，您仍然会遍历每个已创建存储桶的每个元素。因此，您会遍历每个元素。所以总的来说你还是O(n)。

于 2013-09-08T13:16:30.403 回答
1

有了 Eran 的回答，你已经知道你的推理出了什么问题。

但无论如何，有一个定理叫做主定理，它有助于递归函数的运行时间分析。

它符合以下等式：

T(n) = a*T(n/b) + O(n^d)

其中 T(n) 是大小为 n 的问题的运行时间。

在您的情况下，递推方程将是T(n) = 2*T(n/2) + O(1)So a=2、b=2和d=0。之所以如此，是因为对于您的问题的每个 n 大小的实例，您将其分解为大小为 n / 2 (b) 的 2 (a) 个子问题，并将它们组合成 O(1) = O(n^0) .

主定理简单地陈述了三种情况：

如果a = b^d，则总运行时间为O(n^d*log n)

如果a < b^d，则总运行时间为O(n^d)

如果a > b^d，则总运行时间为O(n^(log a / log b))

您的情况与第三个匹配，因此总运行时间为 O(n^(log 2 / log 2)) =O(n)

尝试了解这三种情况背后的原因是一个很好的练习。它们只是以下情况：

1st）我们为每个递归级别做相同数量的总工作（这是合并排序的情况），所以我们只需将合并时间 O(n^d) 乘以级别数 log n。

2nd）我们为第二个递归级别做的工作比第一个递归级别少，依此类推。因此，总工作量基本上是最后一个合并步骤（第一个递归级别）的工作量，O(n^d)。

3rd）我们为更深层次（你的情况）做了更多的工作，所以运行时间是 O（递归树中的叶子数）。在你的情况下，你有 n 叶子用于更深的递归级别，所以 O(n)。

斯坦福 cousera 课程中有一些简短的视频，非常好地解释了大师方法，可在https://www.coursera.org/course/algo上找到。我相信即使没有注册，您也可以随时预览课程。

于 2013-09-10T22:42:58.673 回答