我遇到了這個反向字串函式：
l = [4,2,1,3,5]
def recReverseString(s):
print('*')
l = len(s)
if l < 2:
return s
return recReverseString(s[int(l/2):]) recReverseString(s[:int(l/2)])
l2 = recReverseString(l)
print(l2)
它列印：
*
*
*
*
*
*
*
*
*
[5, 3, 1, 2, 4]
我列印了 9 顆星。所以，我猜盡管進行了減半操作，但時間復雜度仍然是 O(n) 而不是 O(log n)，這通常是大多數分而治之方法的情況。我說得對嗎？
uj5u.com熱心網友回復：
讓 T(n) 表示 recReverseString 函式的時間復雜度。然后我們有以下等式
// Assuming len(s) is O(1) but slicing would be O(n)
T(n) = 2T(n/2) O(n)
這個方程的解是 O(nlogn)。
以二分查找為例，分治演算法。在二分查找中，遞回呼叫占用陣列的一半。因此，這種情況下的遞回方程是
T(n) = T(n/2) 1
這個方程的解是 O(logn)
uj5u.com熱心網友回復：
我們不妨假設初始序列的長度是 2 的 n 次方。考慮到它len是 O(1) 并且兩次切片和連接兩個串列都是 O(n)，我們可以列出這樣一個等式：
T(n) = 2T(n/2) O(n) (1)
將 n 替換為 n/2，我們可以得到：
T(n/2) = 2T(n/4) O(n/2) (2)
替換logn次后，我們可以得到：
T(2) = 2T(1) O(1) (3)
將等式 2 代入等式 1，我們有：
T(n) = 4T(n/4) 2O(n/2) O(n) = 4T(n/4) 2O(n)
反復代入 logn 次直到方程 3，可以得到：
T(n) = nT(1) logn * O(n) = O(n) O(nlogn) = O(nlogn)
所以你的方法的時間復雜度是O(nlogn)。
uj5u.com熱心網友回復：
您在每個遞回步驟中減半，但是對于一半您呼叫該函式，因此一個呼叫 ==> 兩個子呼叫。
不，分而治之本身沒有復雜性（或至少 O(n)），它取決于你在分割后所做的事情......你可以閱讀分治法或時間復雜度分析，仔細閱讀關于主定理。如果樹以某種方式平衡，則具有復雜性 O(log(n)) 的是二進制搜索。log(n) 是遞回呼叫堆疊的最大高度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/486305.html