[理工] 105 台大資工 資演

[joywilliamjo (joywilliamjoy)]

想請問第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://www.ptt.cc/bbs/Grad-ProbAsk/M.1608647568.A.BBB.html
推 A4P8T6X9: 第一個不行，他要求空間複雜度是常數，那個 array A 就
→ A4P8T6X9: 用掉 n 的空間。
啊粗心了沒看到= =
那直接用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
→ mathtsai: 遇到一個node判斷數值是不是比左大比右小
→ mathtsai: 第3題的a 每格平均有n/m個 放進AVL查找 O(lg(n/m))
→ mathtsai: 不確定這說法對不對
推 alex391a: 他一開始不就說遞迴演算法了
推 A4P8T6X9: 遞回 stack 也算進空間的話，in order 也不行。
推 alex391a: 遞迴當然不算
→ aa871220: 是 O(1+(n/m)喔 很多人都漏掉1
→ aa871220: 更正 O(1+lg(n/m))