完全公开这是一个家庭作业问题,因此,我不会要求具体的解决方案,只是对一些问题的一般答案。问题正文如下:



还有一个额外的规定,算法必须是迭代的,而不是递归的。

1)所以我的第一个问题是,我如何确定算法以对数为基数 3 而不是以对数为基数 2 运行?两者仅相差一个常数因子,因此即使我分析了算法的结构,我怎么知道我是在 Log3(n) 时间内运行,还是仅在 (~0.63)(Log2(n)) 中运行时间?它甚至重要吗?

2)我的印象是二分搜索或多或少是搜索排序数组的标准快速算法,因此除了二分搜索和线性搜索之外,还有哪些其他搜索算法可以从中寻找灵感?

3)有什么我遗漏的,一些规定可以比标准的二进制搜索更快地搜索数组吗?

非常感谢任何帮助,如果这个问题相当具体,对不起,但我认为它的某些部分可以普遍适用。

最佳答案

  • 真,O(log(n)) 不关心 log 是基数 2 还是基数 3。
  • 假设现在的任务是使用不超过一定数量的比较。我们可以证明,在最坏的情况下,在没有常数因子的情况下,在不超过 log3(N) 的比较中解决它是不可能的。对于初学者来说,如果数组有三个元素,那么仅通过一次比较就不可能找到该元素或报告它丢失了。同样,对于九元素数组,两次比较显然是不够的。人们也可以使用鸽巢原理和一些注意来证明大 N 是不可能的,尽管我承认我没能在几分钟内做出简短的证明。
    我为大 N 尝试的证明想法是这样的(尽管细节变得乏味)。如果所有数组元素都是不同的,并且也不同于我们搜索的 X,那么在问 K 个问题后我们只能得到 K 位信息,因此可以区分不超过 2K 的数组段,其中 X 可能是。然后,存在一定长度的段(比如3个元素),其中有一个我们没有比较但仍然可以等于X的元素,将其改为X,我们得到一个反例数组。
  • 关于arrays - 对数基3次搜索算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/39571091/

    10-12 07:39
    查看更多