作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
標題[理工] 105 台大資工 資演
時間Tue Dec 22 22:32:46 2020
想請問第4題的a小題
https://i.imgur.com/vREmkz1.jpg
psuedo code的寫法能不能寫
1. Do in-order traversal
2. putvthe in-order traversal in array A
3. for i in range(1~n-1):
4. if all A[i]<A[i+1] = true:
5. return True
6. else:
7. return False
前面第一行inorder O(n)
後面也是O(n)
請問可以寫這樣嗎@@？
psuedo code不太會寫
然後是第3題的a:
https://i.imgur.com/XFzBP0z.jpg
會是O(log(n/m))是因為在H'也撞到之後用chaining存(O(n/m)，然後再放進AVL tree（對
n/m取log)這樣嗎？
感謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.19.142 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1608647568.A.BBB.html
1F：推 A4P8T6X9: 第一個不行，他要求空間複雜度是常數，那個 array A 就12/22 22:58
2F：→ A4P8T6X9: 用掉 n 的空間。12/22 22:58
啊粗心了沒看到= =
那直接用inorder traversal,每個output都去判斷是否比前一個大這樣呢？
※ 編輯: joywilliamjo (223.138.19.142 臺灣), 12/22/2020 23:03:19
※ 編輯: joywilliamjo (223.138.19.142 臺灣), 12/22/2020 23:08:24
3F：→ mathtsai: 遇到一個node判斷數值是不是比左大比右小 12/23 00:48
4F：→ mathtsai: 第3題的a 每格平均有n/m個 放進AVL查找 O(lg(n/m)) 12/23 00:53
5F：→ mathtsai: 不確定這說法對不對 12/23 00:54
6F：推 alex391a: 他一開始不就說遞迴演算法了 12/23 01:13
7F：推 A4P8T6X9: 遞回 stack 也算進空間的話，in order 也不行。 12/24 07:50
8F：推 alex391a: 遞迴當然不算 12/28 11:33
9F：→ aa871220: 是 O(1+(n/m)喔 很多人都漏掉1 01/11 14:21
10F：→ aa871220: 更正 O(1+lg(n/m)) 01/11 14:21