N久N久没有更新这个东西了。一半是在忙其他事情，一半是确是有点畏惧离散数学部分。今天总结的东西都已经是一个月前的东西了。主要包括下面几个部分
1、算法的定义（无聊的东西……） 2、算法分类（普及一下知识） 3、算法的设计基本方法（非常重要的东西，但是这里只简单提一下） 4、算法复杂度与函数的增长（复杂而又麻烦的东西，用简单的语言随便说一说） 5、几个算法展示
1、算法的定义算法（Algorithm）是一系列解决问题的清晰指令 算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 关于Algorithm有五个特性，也不知道是什么人总结的，总之看看就好，没有深究的必要。
1、有穷性（Finiteness） 算法的有穷性是指算法必须能在执行有限个步骤之后终止 2、确切性(Difiniteness) 算法的每一步骤必须有确切的定义； 3、输入项(Input) 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件； 4、输出项(Output) 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性(Effectiveness) 算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。（也称之为有效性）
PS.《数据结构+算法=程序》的作者叫做尼克劳斯-沃思
2、算法分类
算法可大致分为
基本算法 数论与代数算法 加密算法 排序算法 随机化算法 数据结构的算法--关于链表，队列，堆栈，树等等的算法 图论的算法--和图相关的各种算法 计算几何的算法--包括向量，各种平面立体几何相关的算法 动态规划以及数值分析--将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解检索算法--与搜索类似，但是因为信息的特别性，有非常特别的检索方式 并行算法--区别于串行算法，同时执行独立的计算
3、算法的设计基本方法
1.递推法 它把问题分成若干步，找出相邻几步的关系，从而达到目的。比如过F(N）与F（N-1）有关。利用计算F（1）得出F（2）再得出F（3）……直到得出F（N）。这种就是一个递推的过程一个一个推上去。 2.递归 一个函数不断引用自身，直到引用的对象已知。可以理解是递推发的逆向，但是变得复杂很多。比如同上F（N）与F（N-1）有关，而且知道一个终止条件如F（1）已知。用递归思想计算F（N），那么就必须先算F（N-1），计算F（N-1）要先算F（N-1-1）即F（N-2）……直到计算F（2），利用到F（1）。|||通过F（1）算出了F（2），算出了F（2）就能算出F（3）……最终得到F（N）。这里我用|||把递归过程分隔成两个部分，递|||归。关于递归的更多部分，还会在做专门的总结。 3.穷举搜索法 对可能的解按某种顺序进行逐一枚举和检验。极度暴力的方法，不过往往很好用…… 4.贪婪法 简单的说就是每一步都选择最大的利益，但是这样往往导致最终的结果不是最优解。不过我们还是可以得到一个还不错的解。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况。 5.分治法 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 6.动态规划法 这个东西非常牛逼，要顺便记一下他的简写DP。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。DP给我的感觉就是死咬住最优解，求得到最优解的前一步是什么，然后一路递归到出发点。（不知道有没有计算可以再好好玩一玩）
4、算法复杂度与函数的增长
看一个算法好不好，有很多方面，最简单直观的方法就是分析一个算法的时间复杂度和空间复杂度。 空间复杂度就是估计一下一个算法需要使用到的内存，分析方法与分析时间复杂度类似，而且我们不常需要分析空间复杂度（不是说它不重要！）。
严格的说，我们是没办法算出一个消耗的时间的（除非我们拿到机器上跑）。 不过我们可以算出一个算法遇到一个n规模的问题（或者说输入的数据量为N）时，使用某个算法需要执行多少条语句，这里用个一个函数T（N）表示。 值得一提的是，其实不同的语句执行的速度也是有很大差距的。但是一会我们要分析N趋于无穷大的情况，所有很多小东西都会被忽略掉。
现在我们就来讨论一下T（N）的事，如果有两个功能相同算法，遇到N个数据量时需要执行的语句数分别是T1(N)和T2（N）。现在我们要比较这两个算法的在时间是的好坏，如果N是一个具体的数，那带到函数里计算一下就好了。但是这个不能反映出两个算法的真正实力。所以呢，我们使用的方法是计算当n趋于无穷大时T1(N)/T2(N)。（这里有没有一点点高数上计算无穷小的感觉，其实就是反过来），如果T1(N)/T2(N)在N趋于无穷时，是一个无穷大量，说明T2比T1牛逼。如果是0（即无穷小量）就反过来。如果出来是一个常数，说明T1和T2同阶级，如果常数刚好是1，那么这两个算法就在时间复杂度上就一样了。比较时间复杂度本质上就是比较几个T（N）之间函数的相对增长率。
到这里，我们就可以比较两个算法的时间复杂度了，然而如果有四五种算法要比较好坏，两两相比的方法似乎比较麻烦。于是我们想说能不能定义一些等级，看一看每个算法属于什么登记就可以估计他的复杂度。具体的做法是构造一个函数F(N),通常是弄成下面几种F(N) = 1F(N) = logNF(N) = NF(N) = N logNF(N) = N2F(N) = N3F(N) = 2NF(N) = N!这些级别之间的差异，很多书上都有列表和函数图来让你体会，我就偷懒一下不贴图了。接下来呢，比较T(N）和F(N)中的一个确定T(N)所在的等级。
这里要先介绍几个定义和符号。当N很大时（趋于无限），T(N) <= cF(N)，c为一个常数，我们记为T(N) = O(F(N)); 读 大O……当N很大时（趋于无限），T(N) >= cF(N)，c为一个常数，我们记为T(N) = Ω(F(N)); 读 omega当T(N) = O(G(N)) 且 T(N) = Ω(G(N)) 记为T(N) = Θ(G(N))；读 theta当T(N) = O(G(N)) 且 T(N) ！= Ω(G(N)) 记为T(N) = o(G(N))；读 小o……
这里解释一下常数c，这个只是为了消除同阶级之间的差别，也就是上面有写到的T1(N)/T2(N)=一个常数，不论这个常数是什么，1也好，0.00000001，或者1000000我们都把他们看作在同一个等级。因为相比于无穷大和无穷小，常数级别的差异都可以忽略。定义一说明T(N)增长率大于等于F（N），第二个反过来。第三个说明两个函数增长率同阶（相等，忽略常数）。第四个说明T（N）增长率严格小于G(N)。理论上有这么多东西，但是我们往往只求O(F(N))，保证得到一个上界，也就是所谓的大O标记法
下面我们来看几个例子，看一看算法的时间复杂度在代码上的体现。
常数复杂度O（1）
1: int sum = 0, n = 100; /*执行一次*/ 2: sum = (1+n)*n/2; /*执行第1次*/ 3: sum = (1+n)*n/2; /*执行第2次*/ 4: sum = (1+n)*n/2; /*执行第3次*/ 5: sum = (1+n)*n/2; /*执行第4次*/ 6: sum = (1+n)*n/2; /*执行第5次*/ 7: sum = (1+n)*n/2; /*执行第6次*/ 8: sum = (1+n)*n/2; /*执行第7次*/ 9: sum = (1+n)*n/2; /*执行第8次*/ 10: sum = (1+n)*n/2; /*执行第9次*/ 11: sum = (1+n)*n/2; /*执行第10次*/ 12: printf("%d",sum); /*执行一次*/.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } 这段程序T（N）= 12,这是一个常数，用大O标记法就是F（N）= 1；也就是常数阶级，我们简单的说这个算法的复杂度是O(1)的。这里就体现了一个把常数忽略掉的思想，就算T（N）= 99999999，我们一样认为他的复杂度是O(1)。
对数复杂度O(log n)
1: int count = 1; 2: while (count < n) 3: { 4: count = count * 2; 5: /*时间复杂度为O(1)的程序步骤序列*/ 6: }.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }
这个相比其他的稍微难理解一点，不过好在它有一个最经常出现的规律法则算法把问题的大小削减成一部分（通常是1/2），他的复杂度就是O（log n）。比如一开始问题规模是n，一条或几条语句（严格的说是一个O（1）的算法）之后，问题的规模只剩下n/2(或者是削减到其他大小的规模)，我们可以认定他的复杂度为O(log n)
线性复杂度O(n)
1: for(int i = 0; i < n; i++) 2: { 3: /*时间复杂度为O(1)的程序步骤序列*/ 4: } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }
这个不难理解他的复杂度就是O(n).
这里在做一个补充，如果算法如下
1: for(int i = 0; i < 10; i++) 2: { 3: //DoSomething; 4: } 5: 6: for(int j = 0; j < m; j++) 7: { 8: //DoSomething; 9: } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } 这边第一个循环我们可以看成是一个O(1)的复杂度,第二个循环是O(n)的复杂度，那么整体的复杂度我们认为是O(n)。也就是取比较大的复杂度 法则是这样的如果T1（N） = O（F（N）），T2 = O（G（N）），则T1（N）+ T2（N）= max（O（F（N）），O（G（N）））O(n log n)--这个应该叫什么呢？
基本思想是 n log n = log nn然后就可以参考对数阶级的方面，这个复杂度往往会在递归算法中出现，自己水平不行，遇到这个复杂度的算法往往分析不清楚。
平方阶级的复杂度O(n2)
1: int i,j; 2: for(i = 0; i < n; i++) 3: { 4: for (j = 0; j < n;j++) 5: { 6: /*时间复杂度为O(1)的程序步骤序列*/ 7: } 8: } 很清楚这个复杂度就是O(n2) 看两段有一点不一样的算法 1: int i,j; 2: for(i = 0; i < m; i++) 3: { 4: for (j = 0; j < n; j++) 5: { 6: /*时间复杂度为O(1)的程序步骤序列*/ 7: } 8: } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }这个的T（N）= m * n ,由于m,n之间的差别是常数级别的所以我们认为他的复杂度为O(n2)
1: int i,j; 2: for(i = 0; i < n; i++) 3: { 4: for (j = i; j < n; j++) /*注意int j = i而不是0*/ 5: { 6: /*时间复杂度为O(1)的程序步骤序列*/ 7: } 8: } 这边呢？需要一点点数学的东西，他的T（n）= .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }出现线性复杂度和平方复杂度，我们取复杂度大的，然后无视掉1/2常数，所以最终复杂度为O(n2)
关于立方级别的复杂度O(n3)和平方分析相同，就是多嵌套一层循环罢了，再高的常数次方都一样。
指数级O(2n)的和阶乘级O(n!)别的，太少见了，而且这个复杂度是在大的可怕。
复杂度分析中，最最麻烦的就是遇到递归算法，那些能把递归算法玩弄于鼓掌之间的人我们一律称为神。
5、几个算法展示 //冒泡排序 void bubbleSort(int n, int* number) { int i; int j; for(i = 0; i < n; i++) { for(j = 1; j < n - i; j++) { if(number[j] < number[j - 1]) { int tmp = number[j]; number[j] = number[j - 1]; number[j - 1] = tmp; } } } } //选择排序 void selectionSort(int n, int* number) { int i; int j; for(i = 0; i < n; i++) { int min = number[i]; int minIndex = i; for(j = i; j < n; j++) { if(number[j] < min) { min = number[j]; minIndex = j; } } int tmp; tmp = number[i]; number[i] = min; number[minIndex] = tmp; } } //二分查找 bool binarySearch(int* number, int left, int right ,int key) { int mid; while (left <= right) { mid = (left + right) / 2; if(number[mid] == key) { return true; } else { if(key > number[mid]) { left = mid + 1; } else { right = mid -1; } } } return false; } //贪心算法实例 /* 这货不是背包问题。 有N个货物，每个货物重量为1，第i个货位的价值为P[i]。你有一个包，容量为V。 求能得最大价值 */ //贪心思想，那价值最高的前V个。 int main() { int N = 5; int V = 2; int P[5] = {31,65,2,5,65}; int sum = 0; int i; int j; for(i = 0; i < N; i++) { for(j = 1; j < N - i; j++) { if(P[j] > P[j - 1]) { int tmp = P[j]; P[j] = P[j - 1]; P[j - 1] = tmp; } } } for(i = 0; i < V; i++) { sum += P[i]; } printf("%d ", sum); system("pause"); return 0; } //动态规划简单例子.基本背包问题 /* 有N件物品和一个容量为V的背包。 第i件物品的费用是c[i]，价值是w[i]。 求解将哪些物品装入背包可使价值总和最大。 */ /* 定义状态:f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值 “将前i件物品放入容量为v的背包中”这个子问题， 若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。 如果不放第 i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]； 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”， 此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 状态转移方程:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} */ int main() { int N = 5; int V = 30; //为边界设置方便第0件物品都设置成0 int c[6] = {0,9,12,16,5,15}; int w[6] = {0,19,15,18,8,22}; int f[6][31]; int i; int j; //初始化 for(i = 0; i <= N; i++) { for(j = 0; j <= V; j++) { f[i][i] = 0; } } //递推 for(i = 1; i <= N; i++) { for(j = c[i]; j <= V; j++) { if(f[i-1][j] > f[i-1][j-c[i]]+w[i]) { f[i][j] = f[i-1][j]; } else { f[i][j] = f[i-1][j-c[i]]+w[i]; } } } printf("%d ",f[N][V]); system("pause"); return 0; }