最近打算学习一下算法，以下记录我的学习之路。
(一) 算法的概念：
算法 (Algorithm)，是对特定问题求解步骤的一种描述。
解决一个问题往往有不止一种方法，算法也是如此。那么解决特定问题的多个算法之间如何衡量它们的优劣呢？有如下的指标：
(二) 衡量算法的指标
1.时间复杂度：执行这个算法需要消耗多少时间
2.空间复杂度：这个算法需要占用多少内存空间
同一个问题可以用不同的算法解决，而一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于为特定的问题选择合适算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑
算法在时间的高效性和空间的高效性之间通常是矛盾的。所以一般只会取一个平衡点。通常我们假设程序运行在足够大的内存空间中，所以研究更多的是算法的时间复杂度
(三) 算法的时间复杂度
1.语句频度T(n)
一个算法执行所花费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。
但我们不可能对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
而且一个算法花费的时间与算法中的基本操作语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度，记为T(n)。
2.时间复杂度
在刚才提到的语句频度中，n称为问题的规模，当n不断变化时，语句频度T(n)也会不断变化。
但有时我们想知道它的变化呈现什么规律。为此，我们引入时间复杂度概念。
一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+5n+6 与 T(n)=3n²+3n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。
3.常见的时间复杂度有
常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n^3)， k次方阶O(nk)，指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
4.均时间复杂度和最坏时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间
最坏情况下的时间复杂度称最坏时间复杂度。
一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长
5.如何求时间复杂度：
例子1
如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
public static void main(String[] args) {
int x = 91;
int y = 100;
while (y > 0) {
if (x > 100) {
x = x - 10;
y--;
} else {
x++;
}
}
}
该算法的时间复杂度为：O(1)
这个程序看起来有点吓人，总共循环运行了1100次，但是我们看到n没有?
没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数
例子2
int x = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 1; k <= j; k++) {
x++;
}
}
}
该算法的时间复杂度为：O(n^3)
该程序段中频度最大的语句是第5行的语句，内循环的执行次数虽然与问题规模n没有直接关系，
但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此该程序段的时间复杂度为 O(n^3)
当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
例子3
算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 在数值 A[n-1，n-2 …0] 中查找给定值k的算法大致如下
int i = n - 1;
while (i >= 0 && (A[i] != k)) {
i--;
}
return i;
该算法的时间复杂度为：O(n) 此算法中第3行语句的频度不仅与问题规模n有关，
还与输入实例A中的各元素取值和k的取值有关：如果A中没有与k相等的元素，那么第3行语句的频度为 f(n)=n ，该程序段的时间复杂度为 O(n)
可查看原文