算法的概念
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般的，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址以后再调用。
算法是独立存在的一种解决问题的方法和思想。
算法的五大特性
- 输入：算法具有0个或者多个输入
- 输出：算法至少有1个或者多个输出
- 有穷性：算法在优先的步骤之后会自动结束而不会无限循环，并且每一步步骤可以在可接受的时间内完成。
- 确定性：算法的每一步都有确定的含义，不会出现二义性。
- 可行性：算法的每一步都是可行的，也就是说每一步都是能够执行有限的次数完成。
案例引入
如果 a+b+c=1000，且 a2+b2=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('elapsed: %f' %(end_time - start_time))
print('complete!')
运行结果
import time
start_time = time.time()
# 注意是两重循环
for a in range(0, 1001):
for b in range(0, 1001-a):
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("elapsed: %f" % (end_time - start_time))
print("complete!")
执行结果
算法效率衡量
执行时间反映算法效率
实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。
单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的！
程序的运行离不开i计算机的环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度并反应在程序的执行时间上。
时间复杂度与“大O记法”
我们假定计算机执行算法的每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就会代表会花费多少时间单位。对于不同的机器环境而言，确切的单位时间不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上确是相同的，由此我们可以忽略机器环境的影响而客观的反映算法的时间效率。
对于算法的时间效率，用“大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)
算法引入第一种时间复杂度
最坏时间复杂度
分析算法时，存在几种可能的考虑
- 算法完成工作最少需要多少基本操作，即最优时间复杂度
- 算法完成工作最多需要多少基本操作，即最坏时间复杂度
- 算法完成工作平均需要多少基本操作，即平均时间复杂度
我们通常关注算法的最坏情况，即最坏时间复杂度。
时间复杂度的几个基本计算规则
- 1基本操作，与数据规模（n）无关，即只有常数项，认为其时间复杂度为0(1)
- 2顺序结构，时间复杂度按加法进行计算
- 3循环结构，时间复杂度按乘法进行计算
- 4条件分支结构，时间复杂度取最大值
- 5判断一个算法的效率时，往往最需要关注操作数量的最高次项，其他次要项和常数可以忽略
- 6在没有特殊说明下，我们所分析的算法的时间复杂度都是指最坏时间复杂度
常见时间复杂度
时间复杂度
时间复杂度之间的关系
