[理工] 资节heap题目的时间复杂度

楼主: seika555 (kakkoii)   2018-08-13 01:38:05
https://imgur.com/BHWaRzE.jpg
想请问关于上述例题 3 该如何判断time complexity 为 O(k) 呢
看不太懂之前抄的 k+(k+1) 是如何来的
还有如果要应用之前递回那边学的公式
可以把他写成 T(n) = 2* T(n/2)... 的这种形式吗 要如何写呢
突然不知道该如何转换 还请帮忙解惑 谢谢
作者: BroccolYee (花椰菜)   2018-08-13 03:18:00
圆圈是内部节点 方形是外部节点 external = internal + 1最糟的情形是x为heap中的最小值因此要找比x大的值需要把整棵树都翻一次但其实整个搜寻也只能地毯式 heap没有规定说自己的孩子跟兄弟的孩子都要小于自己和兄弟递回方程式应该是T(n) = 2*T(n/2) + O(1)比较完当下的node与x后 大于:输出并继续递回小于或等于:停止 大概是这样~

Links booklink

Contact Us: admin [ a t ] ucptt.com