数据结构和算法：兵法！
开发人员必备基本功
有了算法，能达到事半功倍的效果
引入
先来看一道题:
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
枚举法：一个一个数去试
算法的定义：算法是独立存在的一种解决问题的方法和思想。
算法的五大特性
输入: 算法具有0个或多个输入
输出: 算法至少有1个或多个输出
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
解法1：
# 如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的
import time
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,b,c:%d, %d, %d"%(a,b,c))
end_time = time.time()
print("end, the time is%d"%(end_time - start_time))
效果：
a,b,c:0, 500, 500
a,b,c:200, 375, 425
a,b,c:375, 200, 425
a,b,c:500, 0, 500
end, the time is152
Process finished with exit code 0
解法2：
import time
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,b,c:%d,%d,%d"%(a, b, c))
end_time = time.time()
print("end, the time is %d"%(end_time-start_time))
效果：
a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
end, the time is 1
Process finished with exit code 0
每台机器 执行的总时间不同
但是执行基本运算数量大体相同
时间复杂度：程序运行效率的一种衡量方式，用执行运算步骤多少来表示。
算法是解决问题的一个方法，具有通用性，通用性体现在n上。
所以：
函数：T(n) = n^3 * 2
就是程序的时间复杂度
只要分析大概是什么值就可以了，不用分析具体有多大：
计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。
对于算法的时间效率，我们可以用“大O记法”来表示。
“大O记法”：
对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)
如何理解“大O记法”
对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。
最坏时间复杂度：
分析算法时，存在几种可能的考虑：
算法完成工作最少需要多少基本操作，即最优时间复杂度
算法完成工作最多需要多少基本操作，即最坏时间复杂度
算法完成工作平均需要多少基本操作，即平均时间复杂度
时间复杂度的几条基本计算规则
1、基本操作，即只有常数项，认为其时间复杂度为O(1)[所有基本操作都只算一步]
2、顺序结构，时间复杂度按加法进行计算
3、循环结构，时间复杂度按乘法进行计算
4、分支结构，时间复杂度取最大值
5、判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
6、在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度
