这段代码为什么需要这么长时间？

问题描述：

我正在尝试编码的练习问题。以下是代码。我不明白为什么需要这么长时间才能运行。在这里，输入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

我已经等了一分多钟，也没有完成 – Jakub

调试单步或添加打印语句会让你寻找到代码卡住。 –

答

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

如果if语句为false，则不更新变量，并且您有无限循环。

答

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

该位副本你每次函数在递归通过列表的一大块。使用偏移量而不是复制列表可以显着提高性能。

答

如果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

这段代码为什么需要这么长时间？

相关推荐