时间戳

首页 > 解决方案 > 从算法中导出成本函数并证明其复杂度为 O(...)

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

问题描述

当计算每个操作的算法成本为 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) 而言，成本函数是多少？和大O复杂性？

标签： algorithm

解决方案

我承认，我最初对您的伪代码的缩进感到困惑。在MK 的评论提示后，我重新缩进了您的代码，并理解了您对多个变量的含义。

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

k/2的原因是在没有任何其他信息的情况下，我们假设输入e有相同的机会成为数组当前最小值和最大值之间的任何值。如果您知道分布，那么您可以相应地调整预期平均值。但是，通常情况下，预期平均值将是k的常数因子，因此不会影响大O。

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

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

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

推荐阅读