著名计算机科学家沃思(NiklausWirth)提出一个公式：算法 + 数据结构 = 程序，其中算法是程序的灵魂。
01算法的定义及特性
在数学和计算机科学/算学之中，算法/演算法/算则法(algorithm)为一个计算的具体步骤，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和初始输入(可能为空)开始，经过一系列有限而清晰定义的状态最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效可计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年埃米尔·莱昂·珀斯特的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。
一个算法应该具有以下五个重要的特征：
有穷性(Finiteness)算法的有穷性是指算法必须能在执行有限个步骤之后终止；
确切性(Definiteness)算法的每一步骤必须有确切的定义；
输入项(Input)一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
输出项(Output)一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成(也称之为有效性)。
02算法的设计
设计原则
正确性算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义，能正确反映问题的需求，能够得到问题的正确答案。
算法正确大体分为四个层次：
1. 算法程序没有语法的错误。
2. 算法程序对于合法的输入数据能够产生满足要求的输出的结果。
3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。
4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
可读性可读性：算法设计的另一个目的是为了便于阅读，理解和交流。
写代码的目的一是为了计算机执行，另一个为了便于他人阅读，让人理解和交流。
键壮性当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
时间效率高和存储量低设计方法
1)、递归和递推。递归和递推是学习算法设计的第一步。递归算法是把大问题分解成相对较小的问题的过程，而递推就是从小问题逐步推导出大问题的过程。无论递归还是递推，都应该有初始状态。
2)、搜索、枚举及优化剪枝。搜索在所有算法中既是最简单也是最复杂的算法。说它简单，是因为算法本身并不复杂，实现容易；说它最复杂，是因为要对搜索的范围进行一定的控制，不然就会出现超时等问题。搜索技术主要包括广度优先搜索和深度优先搜索。当其余算法都无法对问题进行求解时，搜索或许是唯一可用的方法。搜索是对问题的解空间进行遍历的过程。有时问题解空间相当庞大，完全遍历解空间是不现实的，此时就必须充分发掘问题所包含的约束条件，在搜索过程中应用这些条件进行剪枝，从而减少搜索量。
3)、动态规划(简称DP)。动态规划的特点是能够把很复杂的问题分解成一个个阶段来处理的递推方法，动态规划必须符合两个特点：无后效性(一个状态的抉择不会影响到更大问题的状态的抉择)及最优化原理(一个大问题的最优性必须建立在其子问题的最优性之上)。动态规划是竞赛中经常出现的的类型，而且变化很大(有线性DP，环形DP，树形DP等)，难易跨度大，技巧性强，甚至还有DP的优化等问题。
4)、贪心。贪心算法是所谓的“只顾眼前利益”的算法。其具体策略是并不从整体最优上加以考虑，而是选取某种意义下的局部最优解。当然使用贪心算法时，要使得到的结果也是整体最优的。
5)、分治、构造等。分治就是把问题分成若干子问题，然后“分而治之”；构造是指按照一定的规则产生解决问题的方法。这两种算法都是在合理的分析题目后，通过一定的规律性推导，从而解决问题。快速排序可以认为是利用了分治法。
03算法效率的度量方法
事后统计方法
这种方法主要是通过设计好的测试程序和数据,利用计算机对不同算法编制的程序的运行时间进行时间比较,从而确定算法效率的高低。
缺陷必须根据算法提前编写好测试程序,花费时间精力较大。
运行时间严重依赖硬件以及软件等环境因素,可能会影响算法本身的优劣。
算法的测试数据设计困难,并且程序的运行时间和测试数据的规模有很大关系。
总结事后统计法虽然直观,但是实际困难且缺陷多,很少使用。
事前分析估算方法
在计算机程序编程前，依据统计方法对算法进行估算。
一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
算法采用的策略，方法(算法优劣的根本)
编译产生的代码质量(软件)
问题的输入规模
机器执行指令的速度(硬件)
一个程序的运行时间依赖于算法的好坏和问题的输入规模,所谓问题输入规模的是指输入量的多少。
在分析程序的分析时间时，最重要的是把程序看成是独立于程序设计语言的算法或者是一系列步骤。
分析一个算法的运行时间时，重要的是把基本操作的数量与输入规模关联起来，即基本操作的数量必须表示成输入规模的函数。随着问题输入规模(n)越来越大，它们在时间效率上的差异也就越来越大.
#include
/**
* 1-100求和
* @param end
* @return
*/
int sum(int end){
int result = 0;
for (int i=1;i<=end;i++){
result += i;
}
return result;
}
/**
* 高斯算法
* @param end
* @return
*/
int simpleSum(int end){
int result = (1+end)*end/2;
return result;
}
int main() {
int res = sum(100);
printf("1+2+3+...+100=%d\n",res);
int res2 = simpleSum(100);
printf("1+2+3+...+100=%d\n",res2);
return 0;
}
这两种求1-100以内和的算法随着end数值的增大(不考虑int溢出),算法优劣不言而喻。
04算法的渐进增长
先看几组算法的变化:
A
当n=1时, C要优于A(C的执行次数要比A少),随着n的增加,A要优于C.所以，综上来说A要优于C.
函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的渐近增长快于g(n)。
随着n的不断增大，A,B,C,D算法的常数对总体的执行次数影响可以忽略。
B
C
观察发现,最高次幂大的函数,随着n的增大,n的最高次幂大的结果的变化也大。
时间复杂度
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
渐近记号(Asymptotic Notation)通常有 O、 Θ 和 Ω 记号法。Θ 记号渐进地给出了一个函数的上界和下界，当只有渐近上界时使用 O 记号，当只有渐近下界时使用 Ω 记号。尽管技术上 Θ 记号较为准确，但通常仍然使用 O 记号表示。
一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法.
推导大O阶
用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高项
如果最高项存在且不是1，则去除与这个项相乘的常数。
常数阶以经典的高斯算法求和为例,
/**
* 高斯方法
* @param end
* @return
*/
int simpleSum(int end){
int result = (1+end)*end/2;
printf("result=%d\n",result);
return result;
}
程序执行两步便获取到结果,所以时间复杂度为T(n)=2,按照推导大O阶方法,时间复杂度为O(1).
线性阶以1-100 求和为例:
/**
* 1-100求和
* @param end
* @return
*/
int sum(int end){
int result = 0;
for (int i=1;i<=end;i++){
result += i;
}
return result;
}
for 循环中共执行的次数取决于end的值,所以时间复杂度为T(n)=n ,按照推导大O阶的方法,记做O(n)。
对数阶void logFunc(int n){
int count = 1;
while(count
count = count * 2 ;
}
printf("count=%d\n",count);
}
设循环x次后退出循环(count>=n),即 2^x = n,则：x= logn 。所以时间复杂度为O(logn);
平方阶void square(int n){
int sum = 0;
for (int i=0;i
for (int j=0;j
sum = i+j;
}
}
printf("sum=%d\n",sum);
}
内层循环执行n^2次, 时间复杂度为:O(n^2);
常用时间复杂度，如下表所示：
常见的时间复杂度消耗时间的大小排列:
O(1)< O(logn)< O(n)< O(nlogn)< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)
时间复杂度练习
分析下列各程序段的时间复杂度
(1)
void main() {
int i=1,k=0,n=10;
while (i<=n-1) {
k+=10*i;i++;
}
}
(2)
void main() {
int i=1,k=0,n=100; do {
k+=10*i;i++;
}while (i==n)
}
(3)
void main() {
int i=1,j=0,n=10;
while (i+j<=n)
if (i>j)
j++;
else
i++;
}
(4)
void main() {
int n=10,x=n,y=0;
while (x>=(y+1)*(y+1))
y++;
}
(5)
void main() {
int n=9,i=1; while (i<=n)
i=i*3;
}
(6)
计算斐波拉契数列的时间复杂度。F(n)=f(n-1)+f(n-2)
(7)计算该函数的时间复杂度。F(n)=6f(n-1)-9f(n-2) 即fn=6fn-1-9fn-2 (8)求多项式A(x)的值的算法可直接根据下列两个公式之一来设计：(1)A(x)=anxn+ an-1xn-1 +……+ a1x + a0 (2)A(x)=(…(anx+ an-1)x+…. a1)x)+ a0 根据算法的时间复杂性比较这两种算法的优劣。
答案：(1) O(n)
(2) O(1)
(3) O(n)
(4) O(√n)
(5)O(log3n)
(6)方法：假设F(n)的时间复杂度为T(n),有 t(n)=t(n-1)+t(n-2)<2t(n-1)<2*2t(n-2)<2*2*2t(n-3)<....>
即t(n)2t(n-2)<2*2t(n-4)<2*2*2t(n-8)>....>2n/2t
(1)(n为奇数时，或2n/2t(0),n为偶数时) 即：t(n)>O(2n/2) 所以O(2n/2)
(7)解：令fn=rn，则原式变为rn-6rn-1+9rn-2=0 同除以rn-2 则原式为r2-6r+9=0 如果解出来的是重根的话，则第一个根以rn代入，第2个重根以nrn代入，第3个重根以n2rn代入，第4个重根以n3rn代入，依此类推。解出的两个根为重根，均为3 所以，tn=c1*3n+c2*n*3n 依题意知t0=0,t1=1,代入后得：t0=c1*30+c2*0*30=0 t1=c1*31+c2*1*31=1 解得：c1=0,c2=1/3 则 tn=1/3*n*3n
(8)解：
(1)A(x)=anxn+ an-1xn-1 +……+ a1x + a0
(2)A(x)=(…(anx+ an-1)x+…. a1)x)+ a0 公式一：假设有一专门的子程序用于计算xn ，则x2需运乘法2次，x3需运行乘法3次，xn需运行乘法n次。由此可知，使用公式一时，子程序被调用的次数为n+(n-1)+(n-2)+….+1=n(n+1)/2。公式二：使用一个简单的循环运行n-1次即可。
最坏情况和平均情况
算法(Algorithms)的复杂度(Complexity)是指运行一个算法所需消耗的资源(时间或者空间)。同一个算法处理不同的输入数据所消耗的资源也可能不同，所以分析一个算法的复杂度时，主要有三种情况可以考虑，最差情况(Worst Case)下的，平均情况(Average Case)的， 最好情况(Best Case)下的。
算法的分析也是类似，我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度就是O(n)，这是最坏的一种情况了。
最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间也就是从概率的角度看，这个数字在每一个位置的可能性是相同的，所以平均的查找时间为n/2次后发现这个目标元素。平均情况更能反映大多数情况下算法的表现。平均情况分析就是对所有输入尺寸为n的输入，让算法运转一遍，然后取它们的平均值。当然，实际中不可能将所有可能的输入都运行一遍，因此平均情况通常指的是一种数学期望值，而计算数学期望值则需要对输入的分布情况进行假设。
平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算出来的。
有时候我们还需要知道最好情况是什么，这有两层意义：一是我们想知道如果运气好，能好到什么程度；二是如果我们能够证明好运气与我们同在，当然需要知道运气好的时候算法表现如何。这种最好分析就是在给定输入规模的时候，看看哪种输入能使算法的运行最有效率。当然，有人认为这种最好情况分析有点假：我们可以操控输入来使一个本来很慢的算法表现得很快，从而达到蒙蔽人的效果。
对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。
为什么要分析最坏情况下的算法时间复杂性？
最差情况下的复杂度是所有可能的输入数据所消耗的最大资源，如果最差情况下的复杂度符合我们的要求， 我们就可以保证所有的情况下都不会有问题。
某些算法经常遇到最差情况。比如一个查找算法，经常需要查找一个不存在的值。
也许你觉得平均情况下的复杂度更吸引你，可是平均情况也有几点问题。
第一，难计算，多数算法的最差情况下的复杂度要比平均情况下的容易计算的多，
第二，有很多算法的平均情况和最差情况的复杂度是一样的.
第三，什么才是真正的平均情况？如果你假设所有可能的输入数据出现的概率是一样的话，也是不合理的。其实多数情况是不一样的。而且输入数据的分布函数很可能是你没法知道。
考虑最好情况的复杂度更是没有意义。几乎所有的算法你都可以稍微修改一下，以获得很好的最好情况下的复杂度(要看输入数据的结构，可以是O(1))。怎样修改呢?
预先计算好某一输入的答案，在算法的开始部分判断输入，如果符合，给出答案。
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。
存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\”进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。
分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
举报/反馈
