课程: 编程基础知识：数据结构
今天就开通帐号，24,700 门业界名师课程任您挑！
大 O 表示法
在这个视频中， 我们将一起来学习大 O 表示法。 为什么需要大 O 表示法呢？ 因为在选择数据结构， 或者是评估它是否能满足我们的需求时， 需要有一个客观的比较标准。 大 O 表示法可以帮助我们 用独立于输入规模的方式， 来描述算法的性能或复杂度， 告诉我们这个操作的效率怎么样。 那么，大 O 表示法和数据结构之间， 有什么关联呢？ 对于任何数据结构我们都会执行 比如插入、更新和搜索等操作。 每种操作都有对应的时间复杂度， 表示在不考虑具体输入规模的前提之下， 执行这个操作所需要的大致时间。 通过比较不同数据结构， 在各种操作下的时间复杂度， 我们可以更好地判断， 哪种数据结构最适合当前的使用场景。 接下来，我们来看看， 几种最常见的时间复杂度。 首先是常数时间复杂度。 我们把它记作 O(1)， 意思就是无论输入规模多大， 执行所需要的时间都保持不变。 举个例子，在 Python 的字典中， 插入一个键值对就是 O(1)。 无论字典中已经有一个， 还是有一百个键值对。 插入操作基本上没有时间差别。 接下来是线性时间复杂度， 记作 O(n)。 也就是说，执行时间会随着输入规模的增大 而成比例地增加。 比如说，如果要在一个列表中 逐项查找一个目标元素， 列表越长，查找就越费时。 所以这就是典型的 O(n) 线性增长。 还有平方时间复杂度，O(n2)。 它意味着，当输入量增大时， 执行时间和输入大小的平方成正比。 如果某个操作需要双重循环来完成， 那么随着输入规模的增加， 运行时间就会指数级飙升。 处理大规模数据，自然也就会变得非常缓慢。 需要注意的是，大 O 表示法描述的是 算法在最坏情况下的表现， 不包含最优或者平均情况。 但是，在选择数据结构时， 有时也要考虑平均情况， 或者是特定的使用场景。 不过在通常情况下， 我们最主要还是考虑最坏情况来进行比较。 当然，并不是所有的操作， 都一定是 O(1) 或者是 O(n)。 不同的数据结构会对不同的操作， 比如搜索、插入、删除 或者是特定排序进行优化。 我们在选择数据结构时， 应该根据所需要的操作， 可能的时间复杂度来判断 哪一种数据结构更加适合。
下载课程离线学习
下载课程到移动设备，轻松离线学习。在领英学习 iOS 或安卓版 APP 下载课程