103 成大資工 演算法第2大題

[Ricky]

老師你好~

想問一下這題的 BIG - O 該如何求算呢

[林立宇]

題目沒寫 M 是甚麼

如果是 constant, 那就直接用 Master theorem 可解得

T(n) = O(n^4)

如果要把 M 寫進去

你可以畫顆 recursion tree 出來看看

樹的每一層往下 level cost 依序是

c, 16c, (16^2)c, (16^3)c, ...

根據 initial condition, 因為當 input size = sqrt(M) 時樹會到底

i.e., 最後一層會停在 (n/2^k) = sqrt(M) 時, 此時 k = log(n / sqrt(M))

所以加總所有的 level cost 可得複雜度為

T(n) = O(16^k) = O(16^log(n / sqrt(M))) = O(n^4 / M^2)