当前课程知识点：数据结构 > 第1章 绪论 > 1.5 算法分析与度量 > 讲解（下）
下面我们来看最好、最坏、
平均时间复杂度
有时候，时间复杂度
除了取决于
问题规模n之外，还取决于这n个数据
的具体状态
以冒泡排序为例
冒泡排序可以分为n-1趟
i从n-1开始
一直到1，一共n-1趟
每一趟
进行若干个数的两两比较
如果左边大于右边
交换这两个数
现在，我们举几个具体的例子
比如，现在要排序的数是5
4
3、2，先进行两两比较
5大于4，左边大于右边
交换，变成4和5
然后，5和3比较
左边大于右边，变成3和5
然后，5和2比较
左边大于右边
变成2和5
i等于n-1的时候
这里记录下i值
i等于n-1的时候
我们找到了一个最大的值——5
放在了最右边
然后，i减1
i变成n-2
这时，再进行两两比较
我们发现，依然是左边大于右边
交换成3和4
然后，4和2比较，依然
左边大于右边
交换成2和4
经过第二轮
我们找到了次大值——4，放到这边
比较完毕
然后进行下一趟的比较
所以，一共要经过n-1趟的外层循环
我们现在给出的值，恰好是元素呈
从大到小排列
所以，这个if条件总是成立的
总的执行次数是可以计算出来的
如果我们换另外一种情况
如果元素已经是排好序的呢
比如，1、2、3、4
这时候
经过一趟实际上就够了
比如，我们先比较1和2
左边不大于右边
不用交换
再比较2和3，依然不用交换
再比较3和4，在3对元素进行两两比较的过程当中
我们并没有发现有左边大于右边的情况
所以，就没有必要再进行下一趟排序了
说明整个元素已经排好序了
所以，我们在这个算法的基础上，增加了一些优化的步骤
每次进入内层循环之前
设立了一个标志
swapped
用来标志内层循环是否发生了两两交换
如果发生了，将它置为1
如果没有发生
那就是0
所以，在外层循环
除了i要大于等于1之外
我们还加了个条件
&& swapped，这个就等价于
swapped
不等于零
因为，C语言默认情况下
除了0表示假，其他都表示真
现在这个算法
它的基本步骤总的执行次数，也就是if里面的两条语句
执行了多少次呢
是取决于数据的基本状态的
比如，随便给一个——5、2、7、3、4、6
很难直接判断出这里面执行了多少次
更何况这里是n个数据
数据个数都不固定
所以这时候
我们就要介绍最好的、最坏的、以及平均时间复杂度
最好的情况下
这个if里面的东西
是一次都不执行的
也就是刚才我们说的，1、2、3、4的情况
这时候
既然F(n)是0，是常数，跟n无关
所以，最好的时间复杂度就记成O(1)
最坏的情况下
刚才已经说了
如果元素是呈逆序排列的
从大到小
一定会执行n-1趟
每一趟
这个if语句总要执行
最后，1到n-1累加
就是这么多
当然
前提条件是我们认为这两个语句
是一个整体
如果你认为它是两条语句
可以在这儿乘以2
这个并不重要
就算乘了2
后面还是会忽略掉它的系数
所以这时候，最坏时间复杂度
是n^2
再来看平均时间复杂度。n个数
我们知道，有n!个排列
假设，每一种排列出现的概率是pi
并且，每一种排列出现的概率是相等的
那最后，平均的总的比较次数实际上就是关于F(n)的期望值
那这个也是不太好计算的
因为取决于
每一个具体排列
的状态
所以，我们往往用最坏的时间复杂度来代表复杂度
在没有特别提及的情况下
时间复杂度通常是指最坏时间复杂度
最后
再来看空间复杂度
算法在执行过程当中
除了要耗费CPU资源之外
肯定还需要耗费到内存，算法当中
哪些部分需要耗费到内存呢？第一个，算法自身
算法写成程序之后
经过编译，程序当中的指令、变量、常量，这些都要占据内存
另外
用于输入、输出，也是用于I/O的存储空间
算法在工作的时候
可能还需要一些临时的存储空间
比如，用于存储形参
临时变量
特别是算法
如果是递归形式
递归形式的算法
在执行过程当中，还需要使用到递归工作栈等等
这些空间就是临时空间，算法所需的临时空间的大小就是算法的空间复杂度
注意，是临时空间的大小
算法自身所需的空间、I/O
所需的空间是不计在内的
空间复杂度我们记为S(n)
这里的S很明显就是Space的意思
另外需要说明的是
这门课为什么不太关注空间复杂度呢
第一
大多数算法的空间复杂度
要么是O(1)
也就是跟问题规模n是无关的
比如，刚才的冒泡排序
对10个数排序、对100000个数排序
都只需要一个临时空间
也就是用来交换变量的那个临时空间
跟问题规模n无关
要么是O(n)，算法要处理的问题
规模是多少，就需要多大的临时空间
这时候，算法可优化的余地不大
比如递归
另外，同一个问题的不同算法
它们的时间复杂度往往差异非常大
比如，刚才讲的冒泡排序
它的最坏时间复杂度是n^2，而归并排序
它的时间复杂度是n*log(n)，当n比较大的时候
这二者相差是非常明显的
也就是说，时间复杂度
往往相差很大
但是空间复杂度
相差不会非常大
大多数情况下
目前的内存容量远超于问题规模
这里不包括现在的大数据
海量数据的情况
对于大多数算法来说
最坏情况下
即使完全不考虑内存优化
算法耗费的内存容量
相对于目前计算机的内存容量来说，是很少的
所以从这个角度，我们也不太关心
空间复杂度
另外
编译器、运行环境的自动优化，以及操作系统的虚拟内存，都可以帮助我们一定程度地优化内存
像Java这样的编程语言
它有自动垃圾回收，无用内存
是可以随时自动回收掉的
不需要编程者关心
另外
即使内存不够了，操作系统
也会用外存来模拟内存
所以，不用太担心内存不够的情况
尽管这种情况很少出现
另外
金钱可以买来更多的内存条
但买不来时间，能用钱解决的问题都不是问题
内存不够了
买内存就是了
现在，服务器的内存都可以达到T级别
想一下
所以，不用太关心空间复杂度
但时间就不一样了
一个算法如果能优化一个数量级
那它
节省的时间
是难以用金钱来衡量的
下面，我们来对比一下时间复杂度和空间复杂度
时间复杂度和空间复杂度有时候是难以两全的
就是说，很难做到一个算法耗费的时间又少
同时
耗费的内存又少
比如，冒泡排序和归并排序
冒泡排序
它的时间复杂度，要比归并排序要高一点
但是
它耗费的临时空间，却要比归并排序少一些
各有利弊
第二
如同代码可读性和可扩展性之间的矛盾
有时候，我们写一个代码
想让这个代码的可读性好
它的扩展性就必然要低一些
反过来也是一样
这里举一个例子
现在要打印一个菱形的星号组成的图案
有的人
写的是这样的程序——直接7行printf语句
你说它不满足问题
要求吗
确实满足
而且没有一点问题
但是，它的可扩展性非常差
如果现在不是打印7行
现在要打印9行、11行，或者打印5行
那这个代码要修改很多行
也就是说，它的可扩展性非常差
满足新的需求
要修改很多地方
现在，如果我们写出这样的算法
打印的行数是作为参数的
尽管这个算法里面的步骤，相比前面的算法来说
可读性要差得多
初看上去，不是那么容易理解
但是，它的扩展性却非常好，你要打印几行
传入不同的参数就行了
要打印7行，传入7
要打印9行
要打印11行
随便你传
这里面的代码都不用改
这就是可读性和可扩展性之间的矛盾
就像时间复杂度和空间复杂度一样
所以，通常
我们是牺牲空间
换时间
牺牲时间换空间
这主要取决于你关注哪一方面
本章的课程，我们就讲到这里，同学们，再见！
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
