运行时分析 - 递归函数示例

-1

我必须检查此函数的运行时间。我知道答案是j-i，但我不明白为什么。运行时分析 - 递归函数示例

假设J>时=我

def my_sum(i,j): 
    if i == j: 
     return i 
    mid = (i + j)//2 
    return my_sum(i, mid) + my_sum(mid + 1, j)

没有任何人有任何想法，为什么？

来源

2017-01-24 Shay Kaha

最重要的是，答案是* not * j-i。请显示您为分析代码所做的工作; “我不明白为什么”不是什么问题规范。看起来您没有运行代码，追踪操作或手动模拟它。请这样做，并描述你的发现和你的遗留困惑。 – Prune

这是一个来自测试的问题。在测试后他们发布了这个答案。 –

编辑：

我不好，没有意识到你正在使用 “//”

什么似乎是问题是返回

您使用：

return my_sum(i, mid) + my_sum(mid + 1, j)

让我们举个例子，i = 2，j = 4：

发生了什么：

if i == j: ## false nothing happens here 
    return i 
mid = (i + j)//2 ## mid = (2+4)//2 = 3 
return my_sum(i, mid) + my_sum(mid + 1, j) ## return my_sum(2,3) + my_sum(4,4) 

my_sum (2,3): 
.... 
mid = (2+3)//2 = 2 
return my_sum (2,2) + my_sum(3,3) = 2 + 3 = 5 

my_sum(4,4) = 4

这样：

my_sum (2,3) + my_sum(4,4) = 5 + 4 = 9

这是problaby不是你想要的。

所以这里的问题是，设置返回值为problaby

来源

2017-01-24 19:26:37 epattaro

运行时分析 - 递归函数示例

回答

相关问题