作者seika555 (kakkoii)
看板Grad-ProbAsk
标题[理工] 资节heap题目的时间复杂度
时间Mon Aug 13 01:38:05 2018
https://imgur.com/BHWaRzE.jpg
想请问关於上述例题 3 该如何判断time complexity 为 O(k) 呢
看不太懂之前抄的 k+(k+1) 是如何来的
还有如果要应用之前递回那边学的公式
可以把他写成 T(n) = 2* T(n/2)... 的这种形式吗 要如何写呢
突然不知道该如何转换 还请帮忙解惑 谢谢
--
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.116.213.244
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1534095491.A.14B.html
1F：推 BroccolYee: 圆圈是内部节点 方形是外部节点 external = interna 08/13 03:18
2F：→ BroccolYee: l + 1 08/13 03:18
3F：→ BroccolYee: 最糟的情形是x为heap中的最小值 08/13 03:18
4F：→ BroccolYee: 因此要找比x大的值需要把整棵树都翻一次 08/13 03:18
5F：→ BroccolYee: 但其实整个搜寻也只能地毯式 heap没有规定说自己的孩 08/13 03:18
6F：→ BroccolYee: 子跟兄弟的孩子都要小於自己和兄弟 08/13 03:18
7F：→ BroccolYee: 递回方程式应该是T(n) = 2*T(n/2) + O(1) 08/13 03:18
8F：→ BroccolYee: 比较完当下的node与x後 大於:输出并继续递回 08/13 03:18
9F：→ BroccolYee: 小於或等於:停止 大概是这样~ 08/13 03:18
谢谢楼上 所以O(1)是因为比较heap[i]>x的这行吗
※ 编辑: seika555 (122.116.213.244), 08/13/2018 18:58:26
10F：推 BroccolYee: O(1)是指在常数时间内完成 因此停止应该也可以说是O 08/13 20:40
11F：→ BroccolYee: (1) 不用分那麽细XD 08/13 20:40
哦哦 原来哈哈 谢谢你
※ 编辑: seika555 (122.116.213.244), 08/13/2018 21:30:50