作者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/cn.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