計算峯值搜索算法（2D）的時間複雜度

Question

我想計算二維峯值搜索算法的時間複雜度。但我不知道如何計算它。請任何人逐行解釋並解決它。 他們如何得到這個答案Ɵ（n log m）。從等式T（n，m）= T（n，m/2）+Ɵ（n）。謝謝

以下演講的2D算法和pdf幻燈片。鏈接是http://courses.csail.mit.edu/6.006/fall10/lectures/lec02.pdf

Answer 1

Ɵ(n)不依賴於m，所以我們實際上只是將這些「Ɵ（n）」「幾」次相加。

這個「幾個」是我們可以在得到1之前將m除以2多少次 - 即log2(m)。

所以我們得到Ɵ(n)*log2(m) = Ɵ(n*log2(m))。