這段代碼爲什麼需要這麼長時間？

Question

我正在嘗試編碼的練習問題。以下是代碼。我不明白爲什麼需要這麼長時間才能運行。在這裏，輸入A是六個元素的列表，但它需要超過五秒的時間才能運行。有誰能告訴我這個的原因嗎？

def solution(A): 
    ln=len(A) 
    if ln>1: 
     mid = ln//2 
     left_h=A[:mid] 
     right_h=A[mid:] 
     a=solution(left_h) 
     b=solution(right_h) 
     i=0 
     j=0 

     tmp=0 

     while i<mid and j<ln-mid: 
      if left_h[i]>right_h[j]: 
       tmp+=1 
       i+=1 
       j+=1 
     return a+b+tmp 
    else: 
     return 0 

Answer 1

while i<mid and j<ln-mid: 
    if left_h[i]>right_h[j]: 
     tmp+=1 
     i+=1 
     j+=1 

如果if語句爲false，則不更新變量，並且您有無限循環。

Answer 2

left_h=A[:mid] 
right_h=A[mid:] 

該位副本你每次函數在遞歸通過列表的一大塊。使用偏移量而不是複製列表可以顯着提高性能。

Answer 3

如果left_h[i]>right_h[j]爲假，它將進入無限循環。

你大概的意思

while i<mid and j<ln-mid: 
     if left_h[i]>right_h[j]: 
      tmp+=1 
     i+=1 
     j+=1