算法效率

昨天学习《算法学习与应用从入门到精通》，有一道题是求指定范围内的完美数。完全数（perfect number），又称完美数或完备数，是一些特殊的自然数，满足所有的真因数（即除了自身以外的约数）的和（即因数函数）等于它本身这一条件。刚又看了其性质：

完全数有许多有趣的性质，具体说明如下所示。

它们都能写成连续自然数之和。例如：
6＝1+2+3 28＝1+2+3+4+5+6+7 496＝1+2+3+…+30+31
它们的全部因数的倒数之和都是2，因此每个完全数都是调和数（在数学上，第n个调和数是首n个正整数的倒数和）。例如：
1/1+1/2+1/3+1/6＝2 1/1+1/2+1/4+1/7+1/14+1/28＝2
除6以外的完全数，还可以表示成连续奇立方数之和。例如：28＝1^3+3^3 496＝1^3+3^3+5^3+7^3 8128＝1^3+3^3+5^3+…+15^3 33550336＝1^3+3^3+5^3+…+125^3+127^3
完全数都可以表达为2的一些连续正整数次幂之和。例如：6＝2^1+2^2 28＝2^2+2^3+2^4 8128＝2^6+2^7+2^8+2^9+2^10+2^11+2^12 33550336＝2^12+2^13+…+2^24
完全数都是以6或8结尾。如果以8结尾，那么就肯定是以28结尾。
除6以外的完全数，被9除后都余1。

刚开始第一遍代码只利用了定义，后面加入性质5以及性质6，使得运行效率大为提升。
开始代码用的就是这一定义，具体如下：

初始化代码

这时候只考虑了项目初步实现，没有思考运行效率高低。实际操作中，在确保项目实现的前提下，尽可能在能力允许情况下考虑运行效率。可以提升项目完成进度、锻炼思维能力、有助于其他项目开展。代码如下：

import time


def is_perfect_num(num):
    all_num = []
    if str(num).endswith('6') or str(num).endswith('28'):
        for i in range(1, num):
            if num % i == 0:
                all_num.append(i)
        if num == sum(all_num):
            return (True, all_num)
        return (False, None)

    else:
        return (False, None)


start = time.time()
for i in range(100000, 500000):
    print(i)
    if is_perfect_num(i)[0]:
        print(i, '\t', is_perfect_num(i)[0])
        input('Any key continue')
end = time.time()
print(end - start)

运行时间：6999.964210033417

二次代码

看到完美数性质后，想到可以利用其性质5对项目优化，具体如下：

import time


def is_perfect_num(num):
    all_num = []
    if str(num).endswith('6') or str(num).endswith('28'):
        for i in range(1, num):
            if num % i == 0:
                all_num.append(i)
        if num == sum(all_num):
            return (True, all_num)
        return (False, None)

    else:
        return (False, None)


start = time.time()
for i in range(100000, 500000):
    print(i)
    if is_perfect_num(i)[0]:
        print(i, '\t', is_perfect_num(i)[0])
        input('Any key continue')
end = time.time()
print(end - start)

运行时间：829.6399991512299

终极代码

既然性质5可以优化代码，是否可以利用其他性质继续优化呢？发现了性质6，实现如下：

import time


def is_perfect_num(num):
    all_num = []
    if str(num).endswith('6') or str(num).endswith('28'):
        if num == 6:
            return (True, [1, 2, 3])
        else:
            if num % 9 == 1:
                for i in range(1, num):
                    if num % i == 0:
                        all_num.append(i)
                if num == sum(all_num):
                    return (True, all_num)
                return (False, None)
            else:
                return (False, None)
    else:
        return (False, None)


start = time.time()
for i in range(100000, 500000):
    print(i)
    if is_perfect_num(i)[0]:
        print(i, '\t', is_perfect_num(i)[0])
        input('Any key continue')
end = time.time()
print(end - start)