a我有以下函數計算從到 的所有數字的總和b。我想知道如何找到它的時間復雜度（不使用主定理）。我希望得到直觀的解釋以及如何解決此類問題。def sum_func(a, b): if a == b: return a mid = (a+b) // 2 return sum_func(a, mid) + sum_func(mid+1, b)
1 回答
牛魔王的故事
TA貢獻1830條經驗 獲得超3個贊
Sayn是范圍的大小，即要相加的數字量。將這些數字想象為二叉樹的葉子，其中樹中的每個節點代表一個子范圍，當調用該函數對該節點的子范圍求和時，它會進行兩次遞歸調用，由該節點在二叉樹中的兩個子節點表示。
n有葉子的二叉樹有2*n - 1節點，每個節點代表一次遞歸調用，因此遞歸函數被調用O(n)次。每次調用該函數時，它都會O(1)加上遞歸調用；因此完成的總工作是O(n)。
添加回答
舉報
0/150
提交
取消