解决问题的不同方法的复杂性

Question

我编写了两个不同的python程序来检查一个数字是否为Armstrong。哪种方法更好，复杂性更低？你知道吗

第一种方法：

def isArmstrong(n):
    temp = n
    length=len(str(n))
    sum1,digit=0,0
    while n>0:
       digit = n%10
       n = n//10
       sum1 += digit**length
    if sum1==temp:
        print('Armstrong No')
    else:
       print('Not an Armstrong no')
isArmstrong(371)

第二种方法：

def isArmstrong(n):
    n=str(n)
    sum=0
    for i in n:
        sum += int(i)**len(n)
     if str(sum)==n:              #Edited After Reading Comments
         print('No is Armstrong')
     else:
         print('No is not Armstrong')

isArmstrong(371)

Answer 1

两种算法都有相同的time complexity，但是您应该更喜欢第二种算法，因为它更具可读性。你知道吗

你也可以这样简化它：

def isArmstrong(n):
    l = len(str(n))
    return sum(int(i)**l for i in str(n)) == n

print(isArmstrong(153)) # >> True

NB: There is a mistake in your second solution: sum==n will always be False, since n is a string and sum an integer. Also, sum is a reserved keyword, you should'nt use it as a variable name.

编辑：

如果你真的需要最大的性能，那么是的，第一个解决方案的速度从几纳秒开始就更快了，我认为这是因为它避免了int转换，这似乎比解决方案1的划分要贵一些。你知道吗

但是如果你能抽出一两纳秒的时间，我肯定会建议你选择另外两个，因为它们的可读性要高得多，而且在python中：Readability counts.

如您所见，对于100000次迭代，差异非常小：

import timeit

def isArmstrong1(n):
    temp = n
    length = len(str(n))
    sum1, digit = 0, 0
    while n>0:
        digit = n % 10
        n = n // 10
        sum1 += digit ** length
    return sum1 == temp

def isArmstrong2(n):
    n0, n = n, str(n)
    sum_ = 0
    for i in n:
        sum_ += int(i) ** len(n)
    return sum_ == n0

def isArmstrong3(n):
    sn = str(n)
    ln = len(sn)
    return sum(int(i)**ln for i in sn) == n

print(timeit.timeit(lambda: isArmstrong1(1), number=100000)) # >> 0.16810399199999998
print(timeit.timeit(lambda: isArmstrong2(1), number=100000)) # >> 0.15370833699999997
print(timeit.timeit(lambda: isArmstrong3(1), number=100000)) # >> 0.16646642300000003

print(" -")

print(timeit.timeit(lambda: isArmstrong1(153), number=100000)) # >> 0.208019595
print(timeit.timeit(lambda: isArmstrong2(153), number=100000)) # >> 0.375219658
print(timeit.timeit(lambda: isArmstrong3(153), number=100000)) # >> 0.36911681499999993

print(" -")

print(timeit.timeit(lambda: isArmstrong1(9474), number=100000)) # >> 0.2775220709999999
print(timeit.timeit(lambda: isArmstrong2(9474), number=100000)) # >> 0.407324241
print(timeit.timeit(lambda: isArmstrong3(9474), number=100000)) # >> 0.377674313