内容摘自书籍《漫画算法，小灰的算法之旅》，我认为是最清晰明了的讲解内容。
在程序开发中，运行时间的长短和占用空间的大小，是衡量程序好坏的重要因素。
可以，如果连代码都没有运行，怎么预知代码所花的时间和占用空间呢？由于运行环境和输入规模的影响，代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本操作执行次数。
时间复杂度
场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？
答案自然是 3 X 10 = 30天。
如果面包的长度是 n 寸呢？
此时吃掉整个面包，需要 3 X n = 3n 天。
如果用一个函数来表达这个相对时间，可以记作 T（n） = 3n，执行次数是线性的。
场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？
即为2的n次方为16。以2位底，16的对数，可以简写为log16。
因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。
如果面包的长度是 n 寸呢？
需要 5 X logn = 5logn天，记作 T（n） = 5logn，执行次数是对数计算的。
场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？
答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。
如果面包的长度是 N 寸呢？
无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2,执行次数的常数。
场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？
答案是从1累加到10的总和，也就是55天。
如果面包的长度是 N 寸呢？
此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。
记作 T（n）= 0.5n^2 + 0.5n，执行次数是多项式性计算的。
时间复杂度归纳：
一个算法中的基本语句执行次数称为语句频度或时间频度。记为T(n)。
n变量称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。算法中基本操作重复执行的次数是问题规模n的某个函数。
如何推导出时间复杂度呢？有如下几个原则：
1.如果运行时间是常数量级，用常数1表示；
2.只保留时间函数中的最高阶项；
3.如果最高阶项存在，则省去最高阶项前面的系数。
让我们回头看看刚才的四个场景。
场景1：
T（n） = 3n
最高阶项为3n，省去系数3，转化的时间复杂度为：
T（n） = O（n）。
场景2：
T（n） = 5logn
最高阶项为5logn，省去系数5，转化的时间复杂度为：
T（n） = O（logn）。
场景3：
T（n） = 2
只有常数量级，转化的时间复杂度为：
T（n） = O（1）
场景4：
T（n） = 0.5n^2 + 0.5n
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：
T（n） = O（n^2）
这四种时间复杂度究竟谁用时更长，谁节省时间呢？当n取得足够大时可以得出结论：
O（1）< O（logn）< O（n）< O（n^2）
另外：
1.T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
2.算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。
时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，
随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大
空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。
1.常量空间
当算法存储空间大小固定，和输入规模没有直接的关系时，即此算法空间复杂度为一个常量，可表示为 O(1)。
示例：
void fun1(int n) {
int num = 3;
...
}
2.线性空间
当算法分配的空间是一个线性的集合，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。
示例：
void fun2(int n) {
int[] array = new int[n];
...
}
3.二维空间
当算法分配的空间是一个二维数组集合，并且数组的长度和宽度都和输入的规模n成正比，空间复杂度就记作O(n2)。
示例：
void fun3(int n) {
int[][] matrix = new int[n][n];
...
}
网友评论