首先，需要解释一下经常看到的O(log n) 是什么意思。

大概总结为普通应用都是10，计算机学科是2，编程语言里面是e。

在我们初中最初接触到对数时，学到的log指以10为底的对数，为了简化把下标10去掉,记为log。 以常数e为底的对数，简化下标记为ln。

但是在计算机学科里，不知道为什么流传下来的log为以2为底的对数，但是有的地方比较严谨，还是把下标2给加上了。

注意，在我们实际的编程语言里又不一样了。

编程语言里log代表的恰恰就是我们数学中学到的ln。 不知道具体什么原因流传下来的而且我也不想知道。。。。。

好了，下面进入正题。

时间复杂度

最简单的理解方法为我们小时候经常玩的数数字游戏，从1到100有一百个数字。

1、从1数到100，时间复杂度即为O(n)。

2、从100开始数，每次把数字减半，大概100、50、25、12、6、3、1，那么时间复杂度为O（logn）(以2为底n的对数)。

3、数了1之后在从1数到100，数到2然后从1数到100 .。。。  直到数到100之后再从1数到100。 那么时间复杂度为O(n^2) O n的平方。

 

空间复杂度

一个算法在运行过程中临时占用存储空间大小的量度。

 

附各排序算法空间复杂度和时间复杂度统计