algorithm - 从算法中导出成本函数并证明其复杂度为 O(...)

Question

当计算每个操作的算法成本为 1 时，当 while 循环依赖于多个变量时，它会变得困惑。此伪代码将一个元素插入到堆的正确位置。

input: H[k]  // An array of size k, storing a heap
   e     // an element to insert
   s     // last element in array (s < k - 1)
output: Array H, e is inserted into H in the right place    

s = s+1                 [2]
H[s] = e                [3]
while s > 1:            ]       
   t=s/2                ][3]
   if H[s] < H[t]       ][3]    
     tmp = H[s]         ][3]
     H[s] = H[t]        ][3]
     H[t] = tmp         ][3]
     s = t              ][2]    
   else 
     break              ][1]

return H 

根据 f(n)，成本函数是多少？以及 Big O 复杂性？

Answer 1

我承认，最初我对您的伪代码的缩进感到困惑。在被 M.K's comment 提示后，我重新缩进了您的代码，并理解您关于多个变量的意思。

提示:如果s等于2^k，循环将迭代k次，最坏的情况.预期平均值是 k/2 次迭代。

k/2 的原因是没有任何其他信息，我们假设输入 e 有相等的机会是当前最小值和最大值之间的任何值大批。如果您知道分布，则可以相应地调整预期平均值。不过，通常预期平均值是 k 的常数因子，因此不会影响 big-O。

设n 为堆中元素的数量。因此，成本函数 f(n) 表示函数对大小为 n 的堆的成本。 while 循环之外的函数成本是常量 C₁，因此 f(n) 由 while 循环本身支配，< em>g(n)。循环每次迭代的成本也是常数 C₂，因此成本取决于迭代次数。所以:f(n) = C₁ + g(n+1)。 g(n) = C₂ + g(n/2)。现在，您可以求解 g(n) 的特征方程。请注意，g(1) 为 0，g(2) 为 C₂。

所提供的算法使用交换将元素冒泡到正确的位置。为了使内部循环更高效(请注意，它不会改变复杂性)，内部循环的行为可以更像插入排序的行为，并且仅在末尾将元素放在正确的位置。

s = s+1
while s > 1 and e < H[s/2]:
   H[s] = H[s/2];
   s = s/2;
H[s] = e;