如果我编写两个软件来计算相同的东西，但其中一个的速度是它的两倍。这是否意味着不同的复杂程度？

Question

对于给定的余额和利率，我的程序计算一年内还清债务的最低月付款额。然而，一个平均在 ~0.000150s 内计算它，另一个在 ~0.000300s 内计算它。这是否意味着不同程度的渐近复杂性？

这些是代码示例：

慢一点的：

import time
start_time = time.time()

balance = 999999
annualInterestRate = 0.18
mRate = annualInterestRate/12
high = (((mRate+1)**12)*balance)/12
low = balance/12
guessed = False

def balanceLeft(balance,mRate,minPayment):
    monthsLeft = 12
    while monthsLeft > 0:
        unpaidBalance =  balance - minPayment
        interest = mRate * unpaidBalance
        balance = unpaidBalance
        balance += interest
        monthsLeft -= 1
    return balance

while guessed == False:
    minPayment = (high + low) / 2
    if round(balanceLeft(balance,mRate,minPayment),2) < 0:
        high = minPayment
    elif round(balanceLeft(balance,mRate,minPayment),2)> 0:
        low = minPayment
    else:
        if abs(round(balanceLeft(balance,mRate,minPayment),2) - 0) < 0.01:
            guessed = True

print('Lowest Payment: ',end='')
print(round(minPayment,2))

print("time elapsed: {:.6f}s".format(time.time() - start_time))

更快的那个

import time
start_time = time.time()

annualInterestRate = 0.18
rate = annualInterestRate / 12
monthsLeftr = 12
xCoefficent = 1 + rate
ConstantTerm = 1 + rate
while monthsLeftr > 1:
    xCoefficent = (xCoefficent + 1) * ConstantTerm
    monthsLeftr -= 1


balance = 999999
monthsLeft = 12
while monthsLeft > 0:
    balance = balance * ConstantTerm
    monthsLeft -= 1
minPayment = balance / xCoefficent


print('Lowest Payment: ', end="")
print(round(minPayment,2))

print("time elapsed: {:.6f}s".format(time.time() - start_time))

Answer 1

不，它们不是同一个程序。第一个有一个 while 循环调用一个函数，这个函数有另一个 while 循环 - 看起来，它们都有不同的复杂性。

第一个显然是较慢的（平方复杂度程序）-第二个没有这样的内部循环并且是线性复杂度程序。

Answer 2

绝对不会。

渐近复杂度从不描述绝对的运行ning次，而是描述问题规模增大时的趋势。

在实践中，渐近复杂度较高的算法运行对于小问题实例来说速度较慢的情况极为常见。

Answer 3

翻译成口头想法，您正在尝试求解线性方程 a-b*x=0，在第一种变体中通过二分法求解，在第二种方法中通过直接公式 x = a/b 求解。纯粹从描述来看，第二个变体总是更快，因为第一个变体还需要计算 a 和 b（每一步分别为 b*x）。

你经常会发现，对于存在直接解公式的方程，运行这个公式比任何迭代逼近方法都要快得多。

不幸的是，直接求解公式没有那么多问题类。但是在这里，线性问题总是可以直接解决（高维线性系统的效率参数会发生变化。）

如果我编写两个软件来计算相同的东西，但其中一个的速度是它的两倍。这是否意味着不同的复杂程度？

If I write two pieces of software that compute the same thing but one does it twice as fast. Does that imply different orders of complexity?

python

algorithm

complexity-theory

python-3.x