algorithm - 检查排序数组上的算法

Question

我有一个排序的长度数组，n我正在使用线性搜索将我的值与数组中的每个元素进行比较，然后我对大小数组执行线性搜索n/2，然后对大小等进行线性搜索n/4，n/8直到我对长度为 1 的数组。在这种情况下，n 是 2 的幂，执行的比较次数是多少？

不确定此响应是否正确，但我认为比较的次数是

T(2 ⁿ ) = (n/2) +(n/4) + ... + 1。

我这样做的原因是因为你必须遍历每一个元素，然后继续添加它，但我仍然不确定。如果有人能引导我完成这个，我将不胜感激

Answer 1

您在问题中设置的重复出现有点偏离，因为如果 n 是输入的长度，那么您不会用 2 ⁿ表示输入的长度。相反，您可以将其写为 n = 2 ^k以选择 k。一旦你有了这个，那么你可以做这样的数学：

• 一半数组的大小为 2 ^k / 2 = 2 ^k-1
• 四分之一数组的大小为 2 ^k / 4 = 2 ^k-2
• ...

如果你总结所有这些值，你会得到以下结果：

2 ^k + 2 ^k-1 + 2 ^k-2 + ... + 2 + 1 = 2 ^k+1 - 1

您可以通过多种方式证明这一点：您可以使用归纳法，或者使用几何级数之和的公式等。这在计算机科学中经常出现，因此值得留心记忆。

这意味着如果 n = 2 ^k，您的算法会及时运行

2 ^k+1 - 1 = 2(2 ^k ) - 1 = 2n - 1

所以运行时间是 2n - 1，也就是 Θ(n)。

希望这可以帮助！