想请问第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)这样吗？
感谢大家

第一个不行，他要求空间复杂度是常数，那个 array A 就用掉 n 的空间。

遇到一个node判断数值是不是比左大比右小第3题的a 每格平均有n/m个 放进AVL查找 O(lg(n/m))不确定这说法对不对

他一开始不就说递回算法了

递回 stack 也算进空间的话，in order 也不行。

递回当然不算

是 O(1+(n/m)喔 很多人都漏掉1更正 O(1+lg(n/m))