Research Space for Linear Algebra & Discrete Mathematics
1. 假設這程式的執行時間為T(n), 這程式在做的事情就是把 n 個input分成三堆後, 分別遞迴下去做同樣的事, 最後再重新改變他們的排列順序, 在(a)小題, 因為第8行需要Ɵ(n)的時間, 每輪有三堆要再遞迴下去執行, 每堆大小是 n/3, 所以總要花的時間就是 T(n) = 3T(n/3) + Ɵ(n), (b)小題意思也差不多, 差別只在第8行只要花constant time就完成了, 所以時間複雜度就是 T(n) = 3T(n/3) + Ɵ(1)2. 一個數只能用一次, 沒有 3+3 這種狀況, 所以要算的就是power set扣掉空集合的元素個數, 因為一個子集會對應到一個sum
摁摁 我了解喏 助教謝謝呦
張貼留言
2 則留言:
1. 假設這程式的執行時間為T(n), 這程式在做的事情就是把 n 個input分成三堆後, 分別遞迴下去做同樣的事, 最後再重新改變他們的排列順序, 在(a)小題, 因為第8行需要Ɵ(n)的時間, 每輪有三堆要再遞迴下去執行, 每堆大小是 n/3, 所以總要花的時間就是 T(n) = 3T(n/3) + Ɵ(n), (b)小題意思也差不多, 差別只在第8行只要花constant time就完成了, 所以時間複雜度就是 T(n) = 3T(n/3) + Ɵ(1)
2. 一個數只能用一次, 沒有 3+3 這種狀況, 所以要算的就是power set扣掉空集合的元素個數, 因為一個子集會對應到一個sum
摁摁 我了解喏 助教謝謝呦
張貼留言