作者HY0869 (冰淇淋)
看板Grad-ProbAsk
标题[理工] 台大107资演
时间Mon Nov 19 09:06:17 2018
https://i.imgur.com/OnM5vLi.jpg
想确定一下答案是
E
D
B
D
B
A
C
吗
顺便问一下第7题是插入n个key还是插入有n个key的树
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.116.247.245
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1542589580.A.46D.html
1F：推 zuchang: Stack 洪逸笔记写O(1) 11/19 12:13
2F：→ zuchang: Hash正常情况是O(1)没错 可是会因为碰撞成worst case的 11/19 12:14
3F：→ zuchang: 话会变O(n) 11/19 12:14
4F：推 zuchang: 第7题我会偏向有n个keys 因为是用with 11/19 12:22
5F：推 kobebset105: Perfect hash 是没有碰撞的喔 11/19 12:29
6F：推 kobebset105: Stack 插入n key 不是 O(1)*n吗 11/19 13:08
7F：推 kcilao110779: 想问一下max heapify从bottom up调整各节点的话会O( 11/20 06:03
8F：→ kcilao110779: n),这样算expected time吗 11/20 06:03
9F：推 st945712: 第四题用bottom up不是O(n)吗(不确定 11/20 17:00
10F：→ kcilao110779: st大我跟你想法一样，只好等版友讨论解答了 11/20 17:29
11F：推 kuan0908: 想问一下bucket sort是哪个呀 11/21 11:33
12F：推 zuchang: stack 应该是指push一个有n个keys 的stack吧 11/21 16:19
13F：推 QQStanGD666: 第四题B 其他一样 12/08 14:01
14F：→ GeniusPuddin: 关於4. 如果是初始n个元素要建一个heap累计是O(N)吧 02/03 23:32
15F：→ GeniusPuddin: MaxHeapify应是假设只有子树root违反heap条件的情况 02/03 23:35
16F：→ GeniusPuddin: MaxHeapify本身应该是O(logN)吧(可能会跑一次树高) 02/03 23:36
17F：→ GeniusPuddin: 但BuildHeap只要从第N/2到1个节点做heapify 共O(N) 02/03 23:37