анализ времени выполнения - рекурсивный пример functiokn

Question

Мне пришлось проверять время выполнения этой функции. Я знаю, что ответ 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) 

делает кого-то есть какие-либо идеи, почему?

Answer 1

редактировать:

мой плохой, не осуществил бы вы использовали "//"

, что, как представляется, проблема возврата

вы используете:

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 установил возвращаемое значение