1. 算法的定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
2. 算法的特性
- 输入：
可以具有零个或多个输入 - 输出：
至少有一个或多个输出 - 可穷性：
指在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。 - 确定性：
- 算法的每一步骤都具有确定的含义，不会出现二义性；
- 算法在一定条件，只有一条执行路径，即相同的输入只能有唯一的输出结果。
- 可行性：
算法的每一步骤都必须是可行的。
3. 算法设计的要求
3.1. 正确性
指算法至少应该具有输入、输出和技工处理无歧义性、能正确反映问题的需求、能够得到问题的真确答案。
大体分为四个层次：
- 算法程序没有语法错误；
- 算法程序对于合法输入能够产生满足要求的输出；
- 算法程序对于非法输入能够产生满足规格的说明；
- 算法程序对于故意刁难的测试输入都有满足要求的输出结果。
3.2. 可读性
便于（他人）阅读（和日后自己阅读和修改）、理解和交流。
3.3. 健壮性
当输入数据不合法时，算法也能做出相关处理，而不是产生异常，崩溃或莫名其妙的结果。
3.4. 时间效率高和存储量低
4. 算法效率的度量方法
- 事后统计方法：通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的云刑事案件进行比较，从而确定算法效率的高低。
缺陷：必须依据算法事先编制好测试程序，通常需要花费大量时间和精力，完了发觉测试的是糟糕的算法，功亏一篑；
不同测试环境差别大。 - 事前分析估算方法：在计算机程序编写前，依据统计方法对算法进行估算。
经过总结，我们发现一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
- 算法采用的策略、方案
- 编译产生的代码质量
- 问题的输入规模
- 机器执行指令的速度
我们举例说明：
第一种算法（求和1）：
int i, sum = 0, n = 100; //执行 1次
for(i = 1; i <= n; i++){ //循环判断语句，执行了n+1次，
sum = sum + i; //执行 n次
}
第二种算法(高斯算法)（求和2）：
int sum = 0, n = 100; //执行 1次
sum = ( 1 + n ) * n / 2; //执行 1次
分析可得：
第一种算法执行了1+(n+1)+n = 2n+2次；
第二种算法，执行了1+1 = 2次，
如果我们把循环看做一个整体，忽略头尾判断的开销，那么这两个算法其实是n和1的差距？
为什么这么说？
第三个例子（求和3）：
int i, i, x = 0; sum = 0, n = 100;
for(i = 1; i <= n; i++){
for(j = 1; j<= n; j++){
x++;
sum= sum + x;
}
}
上面这个例子中，循环条件i从1到100，每次都要让j循环100次，如果非常较真的研究总共精确执行次数，那是非常累的。所以这个例子的算法，需要执行100^2次。
我们研究算法的复杂度，侧重的是研究算法随着输入规模扩大增长量的一个抽象，而不是精确的定位需要执行多少次， 因为如果这样，我们得考虑编译器的优化问题。
- 我们不关心编写程序所用的语言是什么，也不关心这些程序将泡在什么样的计算机上，我们只关心它所实现的算法。
- 不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作。最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
- 我们在分析一个算法的运行时间时，重要的是把基本操作的数量和输入模式关联起来。
5. 函数的渐近增长
给定两个函数f(n) 和 g(n),如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。
示例1：比较算法:
A1=2n+3;
B1=3n+1;
算法的比较一
当n= 1时，A1=5,B1=4，算法A1效率不如算法B1；
当n=2时，A1=7,B1=7，两者效率相同；
当n=3时，A1=9,B1=10，算法A1就开始优于算法B1，随着n的继续增加，算法A1比算法B1逐步拉大差距。所以总体上算法A1比B1优秀。
算法的曲线图对比
经对比中发现，随着n的增大，A2和B2，在曲线表中是被覆盖的，说明后面的+3和+1其实不影响最终的算法变化曲线的。所以我们可以忽略这些加法常数
示例2
算法C是4n+8；算法D是2n^2+1.
算法对比表
算法曲线图
我们观察曲线图发现，去掉与n相乘的常数，即C2与D2，C2与C1重合，D2与D1重合，说明与最高次项相乘的常数也是可以忽略的
示例3
算法G是2n^2 ，算法H是3n+1，算法I是2n^2+3n+1。
算法对比表
算法曲线图
数据很大（即输入规模变得很大）的时候各算法的曲线图如下：
各算法的曲线图
这组数据可以发现，当n的值变得非常大的时候，3n+1已经没法和2n^2的结果相比较，最终可以忽略不计，而算法G跟算法I基本已经重合。
总结
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高项）的阶数。
6. 算法时间复杂度
定义：在进行算法分析时，语句总的执行次数T(n) 是关于问题规模n的函数，进而分析T(n) 随n的变化情况并确定T(n)的数量级。
公式：T(n) = O(f(n))
表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。其中f(n)是问题规模n的某个函数。
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。
显然，三个求和算法的时间复杂度分别可表示为：
O(1),O(n),O(n^2)
分析算法时间复杂度
分析一个算法的时间复杂度（又称推导大O阶）方法：
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项；
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数
- 得到的最后结果就是大O阶。
6.1. 常数阶
举例：
以下这段代码的大O是多少？
int sum = 0, n = 100;
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
printf("hello world\n");
sum = (1 + n) * n / 2;
分析：虽然这段代码虽然有8条语句，但是与问题规模有关系的只有sum = (1 + n) * n / 2;这一句，所以我们记为O(1).
6.2. 线性阶
一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的扩大，对应计算次数成直线增长。
int i, n = 100, sum = 0; //执行 1次
for(i = 1; i <= n; i++){ //循环判断语句，执行了n+1次，
sum = sum + i; //执行 n次
}
这段代码，它的循环的时间复杂度为O(n),因为循环体重的代码需要执行n次。
6.3. 平方阶
嵌套循环：
int i, i, n = 100;
for(i = 1; i <= n; i++){
for(j = 1; j<= n; j++){
printf("hello world\n");
}
}
n等于100时，外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环出来，需要执行100100次，即n的平方。所以这段代码的时间复杂度为O(n^2).
如果有三个嵌套循环，则是n^3.
即：循环的时间复杂度=循环体的复杂度 * 该循环运行的次数
以上的是每个循环的次数都是一样的，如果循环的次数不一样呢？如以下代码：
int i, i, n = 100;
for(i = 0; i < n; i++){
for(j = i; j< n; j++){
printf("hello world\n");
}
}
分析：
当i= 0时，内循环执行了n次，当i=1时，内循环执行n-1次……当i = n-1时，内循环执行1次，所以总的执行次数则为：
n+(n-1)+(n-2)+...+1=n(n+1)/2
拆分后：n^2/2+n/2;
用推导大O的攻略：
第一条忽略，因为没有常数；第二条只保留最高项，所以n/2这项去掉；第三条，去除与最高项相乘的常数，最终得O(n^2)。
6.4. 对数阶
我们看下这个程序：
int i = 1, n = 100;
while(i < n){
i = i * 2;
}
分析：
循环1次时：i = 1 * 2 = 2;
循环2次时：i = 2 * 2 = 4;
循环3次时：i = 4 * 2 = 8;
循环4次时：i = 8 * 2 = 16;
循环5次时：i = 16 * 2 = 32;
循环6次时：i = 32 * 2 = 64;
循环7次时：i = 64 * 2 = 128;
因为128>100,退出循环。
由上面的分析得n=i=2^x(循环次数)，得到x = log(2)n,所以这个循环的时间复杂度为O(logn).
7. 函数调用的时间复杂度分析
我们把问题再实际化一点，看下边的例子：
7.1
int i, j, n;
for(i = 0; i < n; i++){
fun(i);
}
void fun(int count){
printf("%d", count);
}
分析：函数体是打印这个参数，fun函数的时间复杂度为O(1),所以整体的时间复杂度是循环的次数O(n).
如果改成这样呢？
7.2
int i, j, n;
for(i = 0; i < n; i++){
fun(i);
}
void fun(int count){
int j;
for(j = count; j < n; j++){
printf("%d", j);
}
}
事实上，这和我们讲解平方阶时举的第二个例子一样：fun内部的循环次数随count的增加（接近n）而减少，所以fun函数的时间复杂度为O(n),所以整体的时间复杂度为O(n^2).
7.3
n++;
fun(n);
//第一个for循环
for(i = 0; i < n; i++){
fun(i);
}
//第二个for循环
for(i = 0; i < n; i++){
for(j = i; j < n; j++){
printf("%d", j);
}
}
//fun方法
void fun(int count){
int j;
for(j = count; j < n; j++){
printf("%d", j);
}
}
分析：
- n++,为O(1);
- fun(n),为O(n);
- 第一个for循环，为O(n^2);
- 第二个for循环，为O(n^2);
所以整体的时间复杂度：3n^2 +1,根据前面的推导方法，最终的时间复杂度为：O(n^2).
7.4 常见的时间复杂度
常见的时间复杂度.png
常见的时间复杂度的曲线图1.png
常见的时间复杂度的曲线图2.png
7.5 总结
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n!) < O(n^n)
网友评论