時間複雜度的對數函數

Question

程序的最壞情況或平均情況如何依賴於日誌功能？日誌的基礎如何發揮作用？

Answer 1

當您將問題分爲k部分，其大小分別爲n/k，然後對其中一些部分進行「遞歸」（或模仿遞歸）時，會出現日誌因子。

一個簡單的例子是下面的循環：

foo(n): 
    while n > 0: 
    n = n/2 
    print n 

上面將打印n, n/2, n/4, .... , 1 - 有O(logn)這樣的值。
了上述程序的複雜性是O(logn)，因爲每個打印需要的時間常數數量和價值n沿途將得到的數字是O(logn)

如果您正在尋找「現實生活」的例子，在快速排序（爲簡單起見，我們假設分裂爲兩半），則將大小爲n的數組分割爲兩個大小爲n/2的子數組，然後對它們進行遞歸 - 並在每一半上調用該算法。

這使得複雜功能：

T(n) = 2T(n/2) + O(n) 

從master theorem，這是Theta(nlogn)。

同樣，在二進制搜索 - 拆分問題兩個部分，並且只對其中的一個遞歸：

T(n) = T(n/2) + 1 

這將是Theta(logn)

---

該基地是不是因爲

log_k(n) = log_2(n)/log_2(k) 

和log_2（k）是不變的，對於任何缺點tant k。