0

对于我们要查找的元素出现在其中的 2^n-1 个元素的排序数组的二进制搜索，摊销的最坏情况时间复杂度是多少？

在我的期末考试复习表上找到了这个。我什至无法弄清楚为什么我们需要分摊时间复杂度进行二分搜索，因为它最坏的情况是 O(log n)。根据我的笔记，摊销成本计算算法的上限，然后将其除以项目数，所以这不会像最坏情况下的时间复杂度除以 n 那样简单，即 O(log n )/2^n-1?

作为参考，这是我一直在使用的二进制搜索：

public static boolean binarySearch(int x, int[] sorted) {
    int s = 0; //start
    int e = sorted.length-1; //end

    while(s <= e) {
        int mid = s + (e-s)/2;
        if( sorted[mid] == x )
            return true;
        else if( sorted[mid] < x )
            start = mid+1;
        else
            end = mid-1;
    }
    return false;
}
4

2 回答 2

0

老实说，我不确定这意味着什么 - 我看不出摊销如何与二进制搜索相互作用。

也许问题是问成功的二分搜索的平均成本是多少。您可以想象对数组的所有 n 个元素进行二进制搜索并查看此类操作的平均成本。在这种情况下，搜索对一个元素进行一次探测，对两个元素进行两次探测，对四个元素进行三个探测，依此类推。这平均为 O(log n)。

希望这可以帮助！

于 2014-12-08T19:43:06.180 回答
0

iAmortized 成本是所有可能查询的总成本除以可能查询的数量。根据您对未能找到该项目的查询的计数方式，您将获得略有不同的结果。（要么根本不计算它们，要么为每个可能丢失项目的间隙计算一个。）

因此，对于 2^n - 1 个项目的搜索（仅作为保持数学简单的示例），您会在第一个探针上找到一个项目，在第二个探针上会找到 2 个项目，在第三个探针上会找到 4 个, ... 2^(n-1) 在第 n 次探测。缺少的项目有 2^n 个“间隙”（记住将两端都计为间隙）。

使用您的算法，在探针 k 上查找项目需要 2k-1 次比较。（对于第 k 次之前的每个 k-1 探针进行 2 次比较，加上 == 的测试返回 true 的情况。）搜索不在表中的项目需要 2n 次比较。

我会把它留给你做数学，但是当我看到以这种方式编码的二进制搜索时，我不能不表达我是多么恼火的话题。考虑：

public static boolean binarySearch(int x, int[] sorted {
    int s = 0; // start
    int e = sorted.length; // end

    // Loop invariant: if x is at sorted[k] then s <= k < e

    int mid = (s + e)/2;
    while (mid != s) {
        if (sorted[mid] > x) e = mid; else s = mid;
        mid = (s + e)/2; }
    return (mid < e) && (sorted[mid] == x); // mid == e means the array was empty
    }

当您点击您正在寻找的项目时，您不会使循环短路，这似乎是一个缺陷，但另一方面，您只对您查看的每个项目进行一次比较，而不是对每个项目进行两次比较那不匹配。由于一半的项目是在搜索树的叶子中找到的，所以看起来像缺陷的东西实际上是一个主要的收获。实际上，使循环短路有益的元素数量仅约为阵列中元素数量的平方根。

通过算术，计算摊销搜索成本（将“成本”计算为与sorted[mid]的比较次数，您会看到此版本的速度大约是原来的两倍。它还具有恒定成本（在 ±1 比较范围内） , 仅取决于数组中的项目数，而不取决于在哪里或是否找到该项目。这并不重要。

于 2014-12-08T19:59:04.617 回答