想請問第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))