通過復發時，您可以在每次調用這個函數中推導出，時間複雜度爲：T(n) = 2T(n/2) + O(1)這個算法如何O（n）？
，復發樹的高度將是log2(n)，這裏是電話的總數（即節點在樹上）。
教官說這個函數的時間複雜度是O（n），但我簡直看不出原因。
此外，當你替換O（n）轉換的時間複雜度方程有奇怪的結果。例如，
T（n）的< = CN
T（N/2）< =（CN）/ 2
回到原始方程式：
T（n）的< = CN + 1
在哪裏，因爲cn + 1 !< cn
你的教練是正確的，這顯然不是事實。這是Master theorem的應用程序。
你不能像時間複雜度方程中那樣替代O（n），正確的替換將是一個多項式形式，如a + b，因爲O（n）只顯示最高的顯着程度（可以有較低程度的常數）。
要展開的答案，正確地識別形式 T(n) = aT(n/b) + f(n)的時間複雜度方程，具有= 2，B = 2和f（n）的asympt。等於O（1）。 使用這種類型的方程，有三種情況取決於log_b（a）（遞歸成本）和f（n）（解決長度爲n的基本問題的成本）的比較值： 1°f（ n）比遞歸本身長得多（log_b（a）<f（n）），例如a = 2，b = 2和f（n）漸近。等於O（n^16）。然後遞歸是可以忽略的複雜性和總的時間複雜度可以被同化到F的複雜性（N）：°遞歸大於f（n）的（log_b（一）> F（更長
T(n) = f(n)
2 n）），在這裏就是這種情況然後複雜度是O（log_b（a）），在你的例子O（log_2（2））中，即O（n）。 （n）= log_b（a），即存在k> = 0，使得f（n）= O（n^{log_b（a）} log^k（n ）），那麼其複雜性是：
T(n) = O(n^{log_b(a)} log^k+1 (a)}
這是我認爲的醜陋的情況。
也許你可以問這在http://cstheory.stackexchange.com/ – Leo
我不知道存在，謝謝 – sherrellbc