为什么改变平分搜索的实现方式会在同一问题的两个解决方案之间产生运行时间差异?

Question

当我从麻省理工学院的课程中学习python编程问题时，我被卡住了，试图找出两种解决方案之间的区别，或者更具体地说，为什么改变一部分代码使其运行得更快，而原始解决方案花费了很长时间，以至于它一直在运行(没有无限循环)并且从未交付输出。

1. 我的解决方案，永远运行，没有给出输出:

def bisection(i: int, j: int):
"""
Inputs: Integers, 'i' and 'j', representing the lower limit and the upper limit of the search.
Returns: Bisects the number of possibilites and returns the middle value.
"""
high = j
low = i
return (high+low)/2

semiannualraise = .07
rmonthly = 0.04/12
cost = 1_000_000
downpayment = cost*0.25
epsilon = 100
savings = 0
nummonths = 0
startingsalary = float(input("Enter Salary: "))
high = 10000
low = 0
portion_salary= 0
step = 0
salary = startingsalary
monthly_salary=salary/12
while True:
nummonths = 0
salary = startingsalary
while nummonths<36:
portion_of_salary = (bisection(low,high))/10000
step += 1
savings = ((salary/12)*portion_of_salary)+(savings*rmonthly)
nummonths +=1
if nummonths % 6 == 0:
salary = salary + (semiannualraise*salary)

if downpayment-savings < 100 and downpayment-savings >= 0:
break
elif downpayment-savings>= 100:
low = portion_of_salary*10000
else:
high = portion_of_salary*10000
print(f"Best savings rate: {portion_of_salary*100}%")

2. 解决方案

annual_salary = float(input('Enter the starting salary: '))
constant = annual_salary
semi_annual_rate = 0.07
r = 0.04
down_payment = 0.25
total_cost = 1000000
current_savings = 0
months = 0
bisection_count = 0
min = 0 
max = 1
portion_saved = (max/2.0)/1000

if(annual_salary*3<down_payment*total_cost):
print('It is not possible to pay the down payment in three years.')
while(True):
while(months<36):
current_savings += (current_savings*r/12)+(portion_saved*(annual_salary/12))
months+=1
if(months % 6 == 0):
annual_salary += annual_salary*semi_annual_rate
if(current_savings >= down_payment*total_cost+100):
max = portion_saved
portion_saved = max/2.0
bisection_count+=1
months = 0
current_savings = 0
annual_salary = constant
elif(current_savings >= down_payment*total_cost-100 and current_savings <= down_payment*total_cost+100):
break
else:
min = portion_saved
portion_saved = (max+min)/2.0
bisection_count+=1
months = 0
current_savings = 0
annual_salary = constant
print('Best savings rate: ', portion_saved)
print('Steps in bisection search: ', bisection_count)

在我看来，区别只在于我们定义对分搜索的限制的方式，而我无法完全理解那里发生了什么。

注意:虽然我已经使用stackoverflow大约一年的时间来寻找解决方案，这将是我在这里的第一个帖子，它可能是我没有按照如何问一个好问题- stackoverflow问一个好问题。如果是这样，请原谅我，也让我知道我犯了什么错误。谢谢你。

我尝试了以下实现的对分搜索:

def bisection(i: int, j: int):
"""
Inputs: Integers, 'i' and 'j', representing the lower limit and the upper limit of the search.
Returns: Bisects the number of possibilities and returns the middle value.
"""
high = j
low = i
return (high+low)/2

,后来:

high = 10000
low = 0

然后:

elif downpayment-savings>= 100:
low = portion_of_salary*10000
else:
high = portion_of_salary*10000

并期望与另一个解决方案相同的输出，但代码一直在运行。

Answer 1

经过一些调试，我发现第一个代码没有给出输出的原因不是它运行缓慢，而是实际上在这一部分进入了一个无限循环:

while nummonths<36:
portion_of_salary = (bisection(low,high))/10000
step += 1
savings = ((salary/12)*portion_of_salary)+(savings*rmonthly)
nummonths +=1
if nummonths % 6 == 0:
salary = salary + (semiannualraise*salary)
if downpayment-savings < 100 and downpayment-savings >= 0:
break
elif downpayment-savings>= 100:
low = portion_of_salary*10000
else:
high = portion_of_salary*10000

程序永远不会退出while循环，因为它永远不会到达终止条件，即变量储蓄永远不会超过变量首付款。

导致此问题的部分在:

savings = ((salary/12)*portion_of_salary)+(savings*rmonthly)

在这里，程序不是每个月增加节省的金额，而是在每次迭代中给它赋一个新值，并且节省的金额永远不会累积。

只需在'='之前添加缺少的'+':

savings += ((salary/12)*portion_of_salary)+(savings*rmonthly)