1.2.1 算法的好与坏
时间复杂度和空间复杂度究竟是什么呢？首先，让我们来想象一个场景。
某一天，小灰和大黄同时加入了同一家公司。
一天后，小灰和大黄交付了各自的代码，两人的代码实现的功能差不多。
大黄的代码运行一次要花100ms ，占用内存5MB 。
小灰的代码运行一次要花100s ，占用内存500MB 。
于是……
在上述场景中，小灰虽然也按照老板的要求实现了功能，但他的代码存在两个很严重的问题。
1. 运行时间长
运行别人的代码只要100ms，而运行小灰的代码则要100s，使用者肯定是无法忍受的。
2. 占用空间大
别人的代码只消耗5MB的内存，而小灰的代码却要消耗500MB的内存，这会给使用者造成很多麻烦。
由此可见，运行时间的长短和占用内存空间的大小，是衡量程序好坏的重要因素。
可是，如果代码都还没有运行，我怎么能预知代码运行所花的时间呢？
由于受运行环境和输入规模的影响，代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本操作执行次数。
1.2.2 基本操作执行次数
关于代码的基本操作执行次数，下面用生活中的4个场景来进行说明。
场景1 给小灰1个长度为10cm的面包，小灰每3分钟吃掉1cm，那么吃掉整个面包需要多久？
答案自然是3×10即30分钟。
如果面包的长度是n cm呢？
此时吃掉整个面包，需要3乘以n即3n分钟。
如果用一个函数来表达吃掉整个面包所需要的时间，可以记作T(n) = 3n ，n为面包的长度。
场景2 给小灰1个长度为16cm的面包，小灰每5分钟吃掉面包剩余长度的一半，即第5分钟吃掉8cm，第10分钟吃掉4cm，第15分钟吃掉2cm……那么小灰把面包吃得只剩1cm，需要多久呢？
这个问题用数学方式表达就是，数字16不断地除以2，那么除几次以后的结果等于1？这里涉及数学中的对数，即以2为底16的对数log 2 16。（注：本书下文中对数函数的底数全部省略。）
因此，把面包吃得只剩下1cm，需要5×log16即20分钟。
如果面包的长度是n cm呢？
此时，需要5乘以logn即5logn分钟，记作T(n) = 5logn 。
场景3 给小灰1个长度为10cm的面包和1个鸡腿，小灰每2分钟吃掉1个鸡腿。那么小灰吃掉整个鸡腿需要多久呢？
答案自然是2分钟。因为这里只要求吃掉鸡腿，和10cm的面包没有关系。
如果面包的长度是n cm呢？
无论面包多长，吃掉鸡腿的时间都是2分钟，记作T(n) = 2 。
场景4 给小灰1个长度为10cm的面包，小灰吃掉第1个1cm需要1分钟时间，吃掉第2个1cm需要2分钟时间，吃掉第3个1cm需要3分钟时间……每吃1cm所花的时间就比吃上一个1cm多用1分钟。那么小灰吃掉整个面包需要多久呢？
答案是从1累加到10的总和，也就是55分钟。
如果面包的长度是n cm呢？
根据高斯算法，此时吃掉整个面包需要 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为输入规模，刚才的4个场景分别对应了程序中最常见的4种执行方式。
场景1 T(n) = 3n，执行次数是线性 的。
1. void eat1(int n){
2. for(int i=0; i
3. System.out.println("等待1分钟");
4. System.out.println("等待1分钟");
5. System.out.println("吃1cm 面包");
6. }
7. }
场景2 T(n) = 5logn，执行次数是用对数 计算的。
1. void eat2(int n){
2. for(int i=n; i>1; i/=2){
3. System.out.println("等待1分钟");
4. System.out.println("等待1分钟");
5. System.out.println("等待1分钟");
6. System.out.println("等待1分钟");
7. System.out.println("吃一半面包");
8. }
9. }
场景3 T(n) = 2，执行次数是常量 。
1. void eat3(int n){
2. System.out.println(" 等待1分钟");
3. System.out.println(" 吃1个鸡腿");
4. }
场景4 T(n) = 0.5n 2 + 0.5n，执行次数是用多项式 计算的。
1. void eat4(int n){
2. for(int i=0; i
3. for(int j=0; j
4. System.out.println("等待1分钟");
5. }
6. System.out.println("吃1cm 面包");
7. }
8. }
1.2.3 渐进时间复杂度
有了基本操作执行次数的函数T(n)，是否就可以分析和比较代码的运行时间了呢？还是有一定困难的。
例如算法A的执行次数是T(n)= 100n，算法B的执行次数是T(n)= 5n 2 ，这两个到底谁的运行时间更长一些呢？这就要看n的取值了。
因此，为了解决时间分析的难题，有了渐进时间复杂度（asymptotic time complexity） 的概念，其官方定义如下。
若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。
因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法 。
这个定义好晦涩呀，看不明白。
直白地讲，时间复杂度就是把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n 2 、n 3 等。
如何推导出时间复杂度呢？有如下几个原则。
如果运行时间是常数量级，则用常数1表示
只保留时间函数中的最高阶项
如果最高阶项存在，则省去最高阶项前面的系数
让我们回头看看刚才的4个场景。
场景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 ) 。
这4种时间复杂度究竟谁的程度执行用时更长，谁更节省时间呢？当n的取值足够大时，不难得出下面的结论：
O(1)
在编程的世界中有各种各样的算法，除了上述4个场景，还有许多不同形式的时间复杂度，例如：
O(nlogn)、O(n 3 )、O(mn)、O(2 n )、O(n!)
今后当我们遨游在代码的海洋中时，会陆续遇到上述时间复杂度的算法。
1.2.4 时间复杂度的巨大差异
大黄，我还有一个问题，现在计算机硬件的性能越来越强了，我们为什么还这么重视时间复杂度呢？
问得很好，让我们用两个算法来做一个对比，看一看高效算法和低效算法有多大的差距。
举例如下。
算法A的执行次数是T(n)= 100n，时间复杂度是O(n)。
算法B的执行次数是T(n)= 5n 2 ，时间复杂度是O(n 2 )。
算法A运行在小灰家里的老旧电脑上，算法B运行在某台超级计算机上，超级计算机的运行速度是老旧电脑的100倍。
那么，随着输入规模n的增长，两种算法谁运行速度更快呢？
从上面的表格可以看出，当n的值很小时，算法A的运行用时要远大于算法B；当n的值在1000左右时，算法A和算法B的运行时间已经比较接近；随着n的值越来越大，甚至达到十万、百万时，算法A的优势开始显现出来，算法B的运行速度则越来越慢，差距越来越明显。
这就是不同时间复杂度带来的差距。
要想学好算法，就必须理解时间复杂度这个重要的基础概念。有关时间复杂度的知识就介绍到这里，我们下一节再见！