1、算法的概念
算法(Algorithm)的概念在计算机科学领域中几乎无处不在，在各种计算机系统的实现中，算法的设计往往处在核心的位置。计算机的问世是20世纪算法是计算机科学的重要基础，就像算盘一样，人们需要为计算机编制各种各样的“口诀”即算法，才能使其工作。
算法用来描述对特定问题的求解步骤，它是指令的有限序列，其中每一条指令代表一个或多个操作。
软件(项目)=程序+文档
程序=数据结构+算法
软件(项目)= 数据结构+算法 + 文档
2、算法的特征
算法有4大特征：
1 有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步以后结束，且每一步都可以在有穷的时间内完成。
2 确切性：算法中每一个指令都必须有确切的含义，读者和计算机在理解时不会产生二义性。
3 可行性：一个算法是能行的，即算法中描述的操作都是可以通过执行有效次基本运算来实现。
4 输入性：一个算法有零个输入或多个输入，以刻画运算对象的初始情况。
所谓0个输入，就是指算法本身给出了初始条件 int a=5;
3、算法的描述
算法的描述形式多种多样，不同的描述形式对算法的质量有一定的影响。描述同一个算法可以采用自然语言、流程图(盒图)、伪代码以及程序设计语言等，常用的描述算法方法有如下四种:
1 自然语言描述法
最简单的描述算法的方法是使用自然语言，用自然语言来描述算法的优点是简单且便于人们对算法的理解和阅读，缺点是不够严谨，易产生歧义。当算法比较复杂且包含很多转移分支时，用自然语言描述就不是那么直观清晰了。
2 算法框图法
使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁明了、便于理解和交流。
3 伪代码语言描述法
用上述两种方法描述的算法并不能够直接在计算机上执行。为了解决理解与执行之间的矛盾，人们常常使用一种称为伪代码语言的描述方法来对算法进行描述。伪代码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言或算法框图更接近程序设计语言。
4 高级程序设计语言描述法
使用特定的可以直接在计算机上执行的程序描述算法。优点是不用转换直接可以编译执行，缺点是需要对特定的程序设计语言比较理解。大部分的算法最终是需要通过能够向计算机发送一系列命令的程序来实现的。
所谓“程序”是指对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说“数据结构+算法 = 程序”。
程序与算法不同。
程序可以不满足算法的有穷性，例如，操作系统，它是在无限循环中执行的程序，因而不是算法。然而可以把操作系统的各种任务看作一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法实现，该子程序得到输出结果后便终止。
4、算法的标准
在现实社会中，不同的人对于同一问题会有不同的看法或解决方法。同样，在计算机领域，对于同一问题可能存在多种算法也是很自然的事情。例如，对于一批数据的排序问题，就存在多种排序方法。判断一个算法的好坏主要依据以下四个标准。
衡量一个算法的好坏的四个标准：正确性、可读性、健壮性、高效率和低存储量的特征。
1 正确性
算法至少应该具有输出、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
2 可读性
便于阅读、理解和交流。
3 健壮性
当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
4 时间效率高与低存储量需求
时间效率指算法的执行时间，存储量主要指算法程序运行时所占用的内存或外部硬盘空间。设计算法应该尽量本着时间效率高和存储量低的要求。
5、算法的时间复杂度
1、前提
对于一个算法的复杂性分析主要是对算法效率的分析，包括衡量其运行速度的时间效率，以及其运行时所需要占用的空间大小。对于算法的时间效率的计算，通常是抛开与计算机硬件、软件有关的因素，仅考虑实现该算法的高级语言程序。
算法的时间复杂度是一个函数，它定性描述该算法的运行时间，时间复杂度常用 O 表述，它衡量着一个程序的好坏，时间复杂度的估算是算法题的重中之重。
2、概念
要想计算时间复杂度首先得找到该算法中的循环，算法中循环执行的次数就是算法的时间复杂度。
通常时间复杂度用一个问题规模函数来表达：T(n) = O(f(n))
- T(n) 问题规模的时间函数
- n代表的是问题的规模输入数据量的大小
- O时间数量级
- f(n) 算法中可执行语句重复执行的次数
3、算法时间复杂度的计算
1、给定n个元素的 数组a[N],求其中奇数有多少？
分析：判断一个数是偶数还是奇数，只需要判断它除上2的余数是0还是1，把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数就是答案，需要遍历所有的数，因此代码为：
int num = 0;
for (i = 0; i < n; i++)
{if (a[i] % 2){num++;}}由该段代码可知，该函数中只有一层for循环而该循环执行了n次，因此时间复杂度O(n)
2、给定100个元素的 数组a[100],求其中奇数有多少？
时间复杂度O(1)
3、函数内循环为常数次
int fun(int n)
{int i = 0, num = 0;for(; i<100; i++)num++;return num;
}分析：此时时间复杂度为O(1)，这里的1不是指1次，而是指常数次，该循环执行了100次，不管n多大，他都执行100次，所以是O(1)
4、求下面函数的时间复杂度
void func()
{int num = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){num++; // 两层循环，每次循环n次， 因此为n*n}}for (int k = 0; k < N; k++){++num; // 一层循环， 循环n次}for (int l = 0; l < 10; l++){++num; // 一层循环，循环10次}}分析：
由注释，我们可以计算出时间的复杂度的表达式：N*N+N+10，但是我们能写成O(N*N+N+10)吗？
不能，我们知道对于时间复杂度，不需要算出精确的数字，只需要算出这个给算法属于什么量级即可，那么我们又如何知道它属于什么量级呢？
即:我们将字母取无穷大，例如本题中的字母为N，N取无穷大，而10对于N取无穷大后没有影响，因此10可以舍去，原表达式化为 N*N+ N ,再转化为N*(N+1)，由于N为无穷大，因此N+1，也是没有影响的，原式就变成了O(N*N)，也即O(N2)，这就是大无穷(O)渐进表示法，只是一种量级的估算，而不是准确的值。
循环的次数，是一个常数1000 O(1)
循环的次数，是一个n的一次幂n O(n)
循环的次数，是一个n的两次幂 O(n2)
循环的次数是一个复杂项 n*n+n +10,不需要算出精确的数字，只需要算出这个给算法属于什么量级即可 n*n*n + n*n + 10 时间复杂度是：O(n3)
由此可得计算时间复杂度的一般规律(大O表示法)N*N+N+10
1.如果有常数项将其置为1。 N*N+N+1
2.去除表达式中所有加法常数。 N*N+N
3.修改的表达式中 只保留最高阶项，因为只有它才会对最终结果产生影响。 N*N
4.如果最高阶项系数存在且不是1，则将其系数变为1，得到最后的表达式。 N*N
5、计算冒泡排序的时间复杂度
for (i = 0; i < N-1; i++)for (j = 0; j < N-1-i; j++)if(a[j] > a[j+1]){a[j] ^= a[j+1];a[j+1] ^= a[j];a[j] ^= a[j+1];}分析：
例如在这个冒泡排序中,我们需要将无序数组转化为有序数组的一种算法，它并不像上题一样是简单的双层嵌套循环，很容易想到它的循环次数是一个等差数列,第一次循环N-1次,第二次N-2次.....一直到1。
因此 1+2+3+4+...+n = n(1+n)/2 时间复杂度为 O(N2)
通过上面的例子我们看出，大 O 渐近表示法去掉了对结果影响不大的项，简洁明了地表示出了时间复杂度。在实际情况中一般只关注算法的最坏运行情况。
例如在上述冒泡排序中如果给定的数组就已经是有序的了，那么就是它的最好情况，时间复杂度为O(N)。
但是如果有非常多的数据很显然我们看不出它到底是否为最好情况，所以我们必须用最坏的期望来计算所以它是O(N*N)。
