0

我正在为堆编写siftup算法，但我被困在问题的最后。问题的最后一部分说该算法应该具有对数最坏情况时间复杂度，即O(log(n)。我写了下面的算法，其中i是堆中元素的索引，v是堆数组。根的索引是最低的，而它的最大值是堆的最低孩子。我正在考虑数组从 1 到 n

算法

Siftup (v, i) {
While(v[i] > v[i/2] and i != 0) {
    Temp = v[i] // Temp is of the same type as v[i]
    v[i] = v[i/2]
    v[i/2] = temp
    i = i / 2
    }
}

由于该过程涉及四个赋值语句while loop每个语句都具有恒定的最坏情况时序，因此该算法应该具有对数最坏情况时间复杂度。任何人都可以展示一种方法来确定它的O(n)，n堆中元素的数量在哪里？

PS还请让我知道我的算法中的错误。

4

1 回答 1

1

是的，看起来您的算法具有对数复杂度。

我同意您的观察，即每次迭代似乎都具有恒定的复杂性。

之后的步骤是计算对于给定的 N 值将执行多少次迭代。虽然我不会提供直接答案，但这里的关键是i = i / 2. 反过来看这可能更容易：对于某些给定的 N，i在达到 N 之前，您必须加倍（从 1 开始）多少次？i更具体地说，N 的大小与在它至少与 N 一样大之前需要翻倍的次数之间有什么关系？

于 2013-02-14T16:00:24.350 回答