首页 文章

二元搜索的最坏情况复杂化

提问于
浏览 次
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;
}
algorithm search time-complexity binary-search amortized-analysis

2 回答

  • 0

    老实说，我不确定这意味着什么 - 我没有看到摊销如何与二元搜索相互作用 .

    也许问题是询问成功的二元搜索的平均成本是多少 . 您可以想象二进制搜索阵列的所有n个元素并查看此类操作的平均成本 . 在这种情况下，有一个元素，搜索产生一个探针，两个搜索产生两个探针，四个产生三个探针，等等 . 这平均为O（log n） .

    希望这可以帮助！

    回复于
  • 0

    iAmortized cost是所有可能查询的总成本除以可能的查询数 . 您将获得略有不同的结果，具体取决于您如何计算无法找到项目的查询 . （要么根本不计算它们，要么计算缺失项目可能存在的每个间隙 . ）

    因此，对于搜索2 ^ n - 1个项目（仅作为保持数学简单的示例），您可以在第一个探针上找到一个项目，在第二个探针上找到2个项目，在第三个探针上找到4个项目，...第n个探针上的... 2 ^（n-1） . 缺失项目有2 ^ n个“缺口”（记住将两端计为缺口） .

    使用您的算法，在探针k上查找项目需要进行2k-1次比较 . （对于kth之前的每个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
    }

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

    通过算术研究，计算摊销的搜索成本（计算"cost"作为排序[mid]的比较次数，并且你重要的是'll see that this version is approximately twice as fast. It also has constant cost (within ±1 comparison), depending only on the number of items in the array and not on where or even if the item is found. Not that that' .

    回复于

相关问题