算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性:
- 问题是明确的，包含清晰的输入和输出定义。
- 具有可行性，能够在有限步骤、时间和内存空间下完成。
- 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。
算法具有五个基本特性：
- 输入 算法具有零个或多个输入
- 输出 算法至少有一个或多个输出
- 有穷性 指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
- 确定性 算法的每一步骤都具有确定的含义，不会出现二义性
- 可行性 算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成
在算法设计中，我们先后追求以下两个层面的目标。
- 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
- 寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。
也就是说，在能够解决问题的前提下，算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度:
- 时间效率：算法运行时间的长短。
- 空间效率：算法占用内存空间的大小。
简而言之，我们的目标是设计“既快又省”的数据结构与算法。而有效地评估算法效率至关重要，因为只有这样，我们才能将各种算法进行对比，进而指导算法设计与优化过程。
一个算法的时间复杂度（Time Complexity）是指算法运行从开始到结束所需要的时间。这个时间就是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句执行次数（也称为频度）与执行该语句所需时间的乘积。但是，当算法转换为程序之后，一条语句执行一次所需的时间与机器的性能及编译程序生成目标代码的质量有关，是很难确定的。为此，假设执行每条语句所需的时间均为单位时间。在这一假设下，一个算法所花费的时间就等于算法中所有语句的频度之和。这样就可以脱离机器的硬、软件环境而独立地分析算法所消耗的时间。
在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。 一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。 显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别为O(n)，O(1)，O(n²)。 我们分别给它们取了非官方的名称，O(1)叫常数阶、O(n)叫线性阶、O(n²)叫平方阶。
- O(1) : 操作所需的时间是常数(n个元素所需的时间与一个元素所需的时间相同)
- O(n) : n个元素的时间是一个元素时间乘以n
- O(n²): n个元素的时间是一个元素时间乘以n²
推导大O阶：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项相乘的常数。 得到的结果就是大O阶。
顺序结构的时间复杂度。
下面这个算法，也就是刚才的第二种算法（高斯算法），为什么时间复杂度不是O(3)，而是O(1)。
int sum = 0, n = 100; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
printf("%d", sum); // 执行一次
这个算法的运行次数函数是f（n）=3。 根据我们推导大O阶的方法，第一步就是把常数项3改为1。 在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的时间复杂度为O(1)。 那假设是这样:
int sum = 0, n = 100; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
printf("%d", sum); // 执行一次
事实上无论n为多少，上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。注意：不管这个常数是多少，我们都记作O(1)，而不能是O(3)、O(12)等其他任何数字，这是初学者常常犯的错误。
循环结构的时间复杂度。
下面这段代码，它的循环的时间复杂度为O(n)，因为循环体中的代码须要执行n次。
int i;
for (i = 0; i < n; i++) {
// 下面省略时间复杂度为O(1)的程序步骤
...
}下面的这段代码，时间复杂度是多少呢？
int count = 1;
while (count < n) {
count = count * 2;
// 下面省略时间复杂度为O(1)的程序步骤
...
}由于每次count乘以2之后，就距离n更近了一分。 也就是说，有多少个2相乘后大于n，则会退出循环。 由2^x = n得到 x = ㏒(2)N。所以这个循环的时间复杂度为O(㏒n)
下面的例子是一个循环嵌套，它的内循环上面已经分析过，时间复杂度为O(n)。
int i, j;
for (i = 0; i < n; i ++ ) {
for (j = 0; j < n; j ++) {
// 下面省略时间复杂度为O(1)的程序步骤
...
}
}而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n2)。
如果外循环的循环次数改为了m，时间复杂度就变为O(m×n)，如下：
int i, j;
for (i = 0; i < m; i ++ ) {
for (j = 0; j < n; j ++) {
// 下面省略时间复杂度为O(1)的程序步骤
...
}
}所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。那么下面这个循环嵌套，它的时间复杂度是多少呢？
int i, j;
for(i = 0; i < n; i ++) {
for (j = i; j < n; j ++) { // 注意j = i 而不是0
// 下面省略时间复杂度为O(1)的程序步骤
...
}
}由于当i=0时，内循环执行了n次，当i=1时，执行了n－1次，……当i=n－1时，执行了1次。所以总的执行次数为：
用我们推导大O阶的方法:
- 第一条，没有加法常数不予考虑
- 第二条，只保留最高阶项，因此保留n2/2
- 第三条，去除这个项相乘的常数，也就是去除1/2 最终这段代码的时间复杂度为O(n2)。
我们在写代码时，完全可以用空间来换取时间，比如说，要判断某某年是不是闰年，你可能会花一点心思写了一个算法，而且由于是一个算法，也就意味着，每次给一个年份，都是要通过计算得到是否是闰年的结果。还有另一个办法就是，事先建立一个有2050个元素的数组（年数略比现实多一点），然后把所有的年份按下标的数字对应，如果是闰年，此数组项的值就是1，如果不是值为0。这样，所谓的判断某一年是否是闰年，就变成了查找这个数组的某一项的值是多少的问题。此时，我们的运算是最小化了，但是硬盘上或者内存中需要存储这2050个0和1。这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好，其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。
S(n)=O(f(n))若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数，则称这个算法的辅助空间为O(1);
递归算法的空间复杂度:递归深度N*每次递归所要的辅助空间,如果每次递归所需的辅助空间是常数，则递归的空间复杂度是O(N).
空间复杂度的分析方法:
- 一个算法的空间复杂度
S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。 - 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
- 一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；
当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；
当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)。若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
空间复杂度补充:
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。
一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
程序执行时所需存储空间包括以下两部分:
- 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
- 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用
f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差， 即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。 另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法（特别是大型算法）时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。
通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。
当不用限定词地使用“复杂度”时，通常都是指时间复杂度。
顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，
执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。
/**
* 1到100所有素数的和
* 素数就是只能够被1和自身整除的数
*/
public class dd {
public static void main(String[] args) {
int i = 2; // i 即为所求素数
System.out.println("i= " + i);
for (i = 3; i <= 100; i = i + 2) {
boolean f = true;
Label: for (int j = 2; j < i; j++) {
if (i % j == 0) { // if(true)时，i为非素数
f = false;
break Label; // 加了Label貌似只是起到提高效率
}
}
if (f) {// 当f=true时，i为素数。
System.out.println("i= " + i);
}
}
}
}
/**
*古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，
*问每个月的兔子总数为多少？
*
*/
public class aa{
public static void main(String[] args) {
int i = 0;
for (i = 1; i < 20; i++) {
System.out.println(f(i));
}
}
public static int f(int x) {
if(x==1||x==2) {
return 1;
}else {
return f(x-1)+f(x-2);
}
}
}3.有两个有序数组a,b,现需要将其合并成一个新的有序数组。
简单的思路就是先放到一个新的数组中，再排序。但是这样的没体现任何算法，这里考的不是快速排序等排序算法。关键应该是如何利用有序 已知这个条件。可以这样想，假设两个源数组的长度不一样，那么假设其中短的数组用完了，即全部放入到新数组中去了，那么长数组中剩下的那一段就可以直接拿来放入到新数组中去了。
其中用到的思想是:归并排序思想
public static int[] merge(int[] a, int[] b) {
int lengthA = a.length;
int lengthB = b.length;
int[] result = new int[lengthA + lengthB];
//aIndex:用于标示a数组 bIndex：用来标示b数组 resultIndex：用来标示传入的数组
int aIndex = 0, bIndex = 0, resultIndex = 0;
while (aIndex < lengthA && bIndex < lengthB) {
if (a[aIndex] < b[bIndex]) {
result[resultIndex++] = a[aIndex];
aIndex++;
} else {
result[resultIndex++] = b[bIndex];
bIndex++;
}
}
// a有剩余
while (aIndex < lengthA) {
result[resultIndex++] = a[aIndex];
aIndex++;
}
// b有剩余
while (bIndex < lengthB) {
result[resultIndex++] = b[bIndex];
bIndex++;
}
return result;
}数据结构与算法高度相关、紧密结合，具体表现在以下三个方面:
- 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
- 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
- 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!