前言

透过学习B站【清华大学博士讲解Python数据结构与算法】100堂课程来掌握算法精要，并借由博文的写作帮助自己理解，也分享给正在学习的伙伴，大家相互交流、相互学习，相信更能事半功倍。

第 001 章节目录

算法概念
时间复杂度
空间复杂度
复习：递归

[算法概念]

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。[1]

算法简单来说是解决特定问题的方法，一个好的算法将对于程序起到一个至关重大的影响，好的算法将能高效地完成一个程序，不好的算法拖延整体程序的时间不说，甚至有很大的概率会被废弃不用，等于辛辛苦苦写出来的程序无用武之地，平白浪费宝贵的时间。底下举个简单的例子来比较优劣算法的区别有多大。

问题描述：
已知 a+b+c=1000 , 且 a ^ 2 + b ^ 2 = c ^ 2, 求 a, b, c 的所有自然数解。

在读完题目后，相信不少人卷起袖子就开始撸代码了，很大的概率会和以下示例的三重回圈一样，以穷举法来进行求解：

import time

""" 问题描述：
已知 a+b+c=1000 , 且 a^2+b^2=c^2 , 求 a, b, c 的所有自然数解。
"""

# 方法一：三层回圈
start_time = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print("a:%4d + b:%4d + c:%4d = 1000" % (a, b, c), end=" | ")
                print("a^2:%6d + b^2:%6d = c^2:%6d" % (a**2, b**2, c**2))
end_time = time.time()
print("-" * 100, "\nTime Elapsed: %f seconds" % (end_time - start_time))

这就完事了吗？事实证明，代码撸得快，打脸也来得快，不信？请看执行结果：

# 方法一结果
a:   0 + b: 500 + c: 500 = 1000 | a^2:     0 + b^2:250000 = c^2:250000
a: 200 + b: 375 + c: 425 = 1000 | a^2: 40000 + b^2:140625 = c^2:180625
a: 375 + b: 200 + c: 425 = 1000 | a^2:140625 + b^2: 40000 = c^2:180625
a: 500 + b:   0 + c: 500 = 1000 | a^2:250000 + b^2:     0 = c^2:250000
----------------------------------------------------------------------
Time Elapsed: 189.930115 seconds

由上面的例子来看，仅仅1000以内三个回圈的组合来求解都跑了3分钟多一些，确实效能堪忧，看来是有必要换个思路了。回到题意，既然限制条件 a+b+c = 1000，那么，当 a 与 b 都决定了以后，c 不也自然被决定了吗？因此，第三层回圈 c 的范围改为动态根据 a+b 的结果而定，相信可以省一些时间吧，说做就做：

import time

""" 问题描述：
已知 a+b+c=1000 , 且 a^2+b^2=c^2 , 求 a, b, c 的所有自然数解。
"""

# 方法二：三层回圈+动态 c 范围
start_time = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1000-a-b):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print("a:%4d + b:%4d + c:%4d = 1000" % (a, b, c), end=" | ")
                print("a^2:%6d + b^2:%6d = c^2:%6d" % (a**2, b**2, c**2))
end_time = time.time()
print("-" * 70, "\nTime Elapsed: %f seconds" % (end_time - start_time))

结果会是如何呢？好紧张。。。

# 方法二结果
a:   0 + b: 500 + c: 500 = 1000 | a^2:     0 + b^2:250000 = c^2:250000
a: 200 + b: 375 + c: 425 = 1000 | a^2: 40000 + b^2:140625 = c^2:180625
a: 375 + b: 200 + c: 425 = 1000 | a^2:140625 + b^2: 40000 = c^2:180625
a: 500 + b:   0 + c: 500 = 1000 | a^2:250000 + b^2:     0 = c^2:250000
---------------------------------------------------------------------- 
Time Elapsed: 44.859897 seconds

哇哇哇！这效能的提升可以啊，运行时间竟然大幅减少了 76%！好了，打完收工！
。
。
。
吃瓜群众：等等！等等！这位壮士请留步！吾等观壮士的代码清奇，想必壮士的实力远不止如此，肯定有更大的绝招才是！
壮士：这都被你们给看出来了啊？！没错！我这 “含笑半步法” 是用蜂蜜，川贝，桔梗，加上天山雪莲配制成绝佳养生饮品，边喝边码出来滴。。。
导演：（拿动漫专用纸棒用力朝壮士头上敲下）回来！你跑题了！
壮士：（头上带血面带标准一号微笑对着导演）抱歉，我这就言归正传。。。
壮士：是的，既然按照题意 a+b+c=1000，那么当 a 与 b 都决定了以后，c 不也自然被决定了吗？
吃瓜群众：这我们都知道，前面壮士就说过了，然后呢？
壮士：那各位不觉得第三层回圈不就是个累赘吗？直接拿 c = 1000 - a - b 不就得了吗？也就是说只要：

利用两层回圈的 a+b 结果来推算 c，再接着检查此时是否 a ^ 2 + b ^ 2 = c ^ 2 就大功告成了！

验证一下，上代码：

import time

""" 问题描述：
已知 a+b+c=1000 , 且 a^2+b^2=c^2 , 求 a, b, c 的所有自然数解。
"""

# 方法三：二层回圈
start_time = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
        c = 1000-a-b
        if a**2 + b**2 == c**2:
            print("a:%4d + b:%4d + c:%4d = 1000" % (a, b, c), end=" | ")
            print("a^2:%6d + b^2:%6d = c^2:%6d" % (a**2, b**2, c**2))
end_time = time.time()
print("-" * 70, "\nTime Elapsed: %f seconds" % (end_time - start_time))

结果直接拿走，不送：

# 方法三结果
a:   0 + b: 500 + c: 500 = 1000 | a^2:     0 + b^2:250000 = c^2:250000
a: 200 + b: 375 + c: 425 = 1000 | a^2: 40000 + b^2:140625 = c^2:180625
a: 375 + b: 200 + c: 425 = 1000 | a^2:140625 + b^2: 40000 = c^2:180625
a: 500 + b:   0 + c: 500 = 1000 | a^2:250000 + b^2:     0 = c^2:250000
---------------------------------------------------------------------- 
Time Elapsed: 2.000944 seconds