-
算法引入：
如果a+b+c=1000，且a2+b2=c^2（a,b,c为自然数），如何求出所有a，b，c可能的组合？
解决：枚举法 思路：a=0，b=0，c=1/2/3....
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("times:%ds"%(end_time-start_time)) print("finished") 输出： a,b,c:0,500,500 a,b,c:200,375,425 a,b,c:375,200,425 a,b,c:500,0,500 times:261s finished 算法是独立存在的一种解决问题的方法与思想，对于算法而言，实现的语言并不重要，重要的是思想。
-
算法的五大特性
- 输入：算法具有0个或多个输入
- 输出：算法至少有1个或多个输出
- 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
- 确定性：算法中的每一步都有确定的含义，不会出现二义性
- 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
二、复杂度分析
1、算法效率衡量
-
上述例子算法改进：
import time start_time = time.time() for a in range(0,1001): for b in range(0,1001): c = 1000 - a - b #给出了a,b后,c的值就已经是确定下来的了 if a**2 + b**2 == c**2: print("a,b,c:%d,%d,%d"%(a,b,c)) end_time = time.time() print("times:%ds"%(end_time-start_time)) print("finished") 输出： a,b,c:0,500,500 a,b,c:200,375,425 a,b,c:375,200,425 a,b,c:500,0,500 times:2s finished
-
执行时间反应算法效率
由上述的两段程序的执行时间（261秒与2秒），可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。
-
单靠时间值是不绝对可信的！
假设第二次的算法实在一台性能很差的计算机中运行，运行时间可能与第一次运行时间差不了多少，故：单纯依靠运行时间来比较算法的优劣并不一定是客观准确的！程序的运行离不开计算机环境（包括硬件和操作系统），客观原因影响程序运行的速度，即每台机器执行的总时间不同，但是执行的基本运算数量大体相同，故下述引入时间复杂度概念。
2、时间复杂度
（1）什么是大O？
-
n表示数据规模，O(f(n))表示算法所需要执行的指令数，和f(n)成正比。其中f(n)是n的一个函数。
在业界，O(f(n))表示算法执行的最低上界。（更详细概念请百度）记T为执行指令数
上述第一个python代码：T = 1000 * 1000 * 1000 * 2 (三个循环，一条if语句，一条print语句)
若题目变为a+b+c = 2000，则T = 2000 * 2000 * 2000 * 2
改为a+b+c = n ,则T=n * n * n * 2
总结：对于一个算法来说，T与数据规模n有关，即T(n)= n^3*2，当n较大时，T(n)= n^3，常数不计。
算法 所需执行指令数 二分查找法O(logn) a*logn 寻找数组中的最大/最小值O(n) b*n 归并排序算法O(nlogn) c*nlogn 选择排序法O(n^2) d*n^2 对于算法的时间性质与空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分，而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。如上：a,b,c,d均为常数 ，当数据规模较大时，算法消耗的时间复杂度与这些常数关系不大，而是与n所在项相关，故此时一般省略常数！
例如：
算法A：O(n) 所需执行指令数：10000*n
算法B：O(n^2) 所需执行指令数：10*n^2
对比不同n规模时算法A，B的指令数情况：
n A的指令数10000n B的指令数10n^2 倍数 10 10^5 10^3 100 100 10^6 10^5 10 1000 10^7 10^7 1 10000 10^8 10^9 0.1 10^5 10^9 10^11 0.01 10^6 10^10 10^13 0.001 可见，时间复杂度大O衡量的是量级的差异。当n达到某个值时，时间复杂度低的算法一定比时间复杂度高的算法运算时间快，n越大，差距越明显。（数据规模较小时，时间复杂度高的算法有常数上的优势，还是可以使用的，一般情况下，使用复杂度较低的算法更优）
-
若设计的算法有两部分，则整个算法以量级最高的作为主导的时间复杂度。如：
O(nlogn+n)= O(nlogn)
O(nlogn+n^2)$= $O(n^2)
注：上面式子的前提是 ：这两部分对应的规模n是一样的，而像O(AlogA+B)这种类型的，此处A和B的规模可能不一样，故不能省略掉AlogA这部分（对邻接表实现的图进行遍历，时间复杂度是O(V+E)，V是顶点数，E是边数，不能随便替换）
（2）最坏时间复杂度
-
分析算法时，存在几种可能的考虑：
算法完成工作最少需要多少基本步骤，即最优时间复杂度
算法完成工作最多需要多少基本步骤，即最坏时间复杂度
算法完成工作平均需要多少基本步骤，即平均时间复杂度
对于最优时间复杂度，其参考价值不大，反映的是最乐观最理想的情况；对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作；对于平均时间复杂度，全面反映算法的性质，但其也会因为应用算法的实例分布不均匀而难以计算；因此，我们主要关注算法的最坏情况，即最坏时间复杂度
-
算法复杂度在有些情况是用例相关（即与待排数据分布情况有关）的，比如：
插入排序算法O(n^2)：最差情况：O(n^2)；最好情况：O(n) ；平均情况（业界）：O(n^2)
快速排序算法O(nlogn)：最差情况：O(n^2) (随机化情况下，退化成最差情况的概率比较低)；最好情况：O(nlogn)；平均情况（业界）：O(nlogn)
（3）时间复杂度计算
-
时间复杂度的几条计算规则
- 基本操作，即只有常数项，认为其时间复杂度为O(1)
- 顺序结构，时间复杂度按加法计算
- 循环结构，时间复杂度按乘法计算
- 分支结构，时间复杂度取最大值
- 判断一个算法的效率时，往往只需关注操作数量的最高次项，其他次要项和常数项可以忽略
- 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度
常见时间复杂度消耗时间大小：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n!) < O(2^n)-
问题：有一个字符串数组，将数组中每一个字符串按照字母序排序；之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度？
错误解答：把字符串数组长度与每一个字符串的长度都统一当成了n O(n*nlogn+nlogn)=O(n^2log2n) 正确解答： --假设最长的字符串长度为s（因为大O算的是上界）；数组中有n个字符串 --对每个字符串排序：O(slogs) --将数组中的每一个字符串按照字母序排序：O(n*slogs) --将整个字符串数组按照字典序排序：O(s*nlog(n)) （排序算法中nlogn表示的是比较的次数，通常说的对整型数组排序只需进行nlogn次比较，是因为两个整数进行比较在计算机中是O(1)级别的，而此处字符串比较字典序，还需耗费O(s) --综上：O(n*slogs)+O(s*nlog(n))=O(n*slogs+s*nlog(n))=O(n*s*(logs+logn))
