a我有以下函數(shù)計算從到 的所有數(shù)字的總和b。我想知道如何找到它的時間復(fù)雜度（不使用主定理）。我希望得到直觀的解釋以及如何解決此類問題。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條經(jīng)驗 獲得超3個贊
Sayn是范圍的大小，即要相加的數(shù)字量。將這些數(shù)字想象為二叉樹的葉子，其中樹中的每個節(jié)點代表一個子范圍，當調(diào)用該函數(shù)對該節(jié)點的子范圍求和時，它會進行兩次遞歸調(diào)用，由該節(jié)點在二叉樹中的兩個子節(jié)點表示。
n有葉子的二叉樹有2*n - 1節(jié)點，每個節(jié)點代表一次遞歸調(diào)用，因此遞歸函數(shù)被調(diào)用O(n)次。每次調(diào)用該函數(shù)時，它都會O(1)加上遞歸調(diào)用；因此完成的總工作是O(n)。
添加回答
舉報
0/150
提交
取消