舉例來說，之前的naiive multiplication algorithm的recurrence relations如下，用master theorem分析之：
改良過的karatsuba乘法，將subproblem減少成只有三個，所以a = 3，用master theorem分析如下：
大約是O(n^1.58)，這不是常數倍數的改良，是指數的改良，相當的好。
如果有人能把乘法演算法改成只有2個subproblem呢？事實上目前沒發現過，不過這個recurrence relations就是merge sort的特徵：
所以目前sorting最好的running time只能是O(nlogn)。
這個是什麼？沒錯，就是Binary search:
沒有留言:
張貼留言