算法分析——大O标记法

悠悠 2024-04-08 08:25 74阅读 0赞

**目录**

一. 运行时间

二. 大O 表示法

2.1 示例

三. 总结

五. 扩展

--------------------

## 一. 运行时间 ##

> 每次介绍算法时，我们都将讨论其运行时间。一般而言，应选择**效率最高的算法**，以最大限度地减少运行时间或占用空间。
> 
> 可是，如果代码都还没有运行，我怎么能预知代码运行所花的时间呢？
> 
> 由于受运行环境和输入规模的影响，代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本操作执行次数。

> 诸如二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
> 
> 二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多需猜32次。厉害吧？二分查找的运行时间为对数时间（或log时间）。下表总结了我们发现的情况。

![d5e2b8d772ba3b346168605da0c7982c.png][]

--------------------

## 二. 大O 表示法 ##

> 大O表示法是一种特殊的表示法，指出了算法的速度有多快。谁会在乎运算速度呢？实际上，你经常要使用别人编写的算法，在这种情况下，知道这些算法的速度大有裨益。本节将介绍大O表示法是什么，并使用它列出一些最常见的算法运行时间

> 为了解决时间分析的难题，有了**渐进时间复杂度（asymptotic time complexity）**的概念，其官方定义如下：

>  **算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示；若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。**

> 因为渐进时间复杂度用大写O来表示，所以也被称为**大O表示法**。

> 概念有点晦涩，我们使用下面的这个示例来理解一下

### 2.1 示例 ###

> 通过以下示例，来理解算法的运行时间以不同的速度增加：

> 小明要为“**嫦娥5号**”编写一个查找算法，这个算法在火箭即将登陆月球前开始执行，帮助计算着陆地点。
> 
> 前面示例表明，简单查找和二分查找这两种算法的运行时间呈现不同的增速。小明需要做出决定，是使用简单查找还是二分查找。使用的算法必须快速而准确。
> 
> 一方面，二分查找的速度更快。小明必须在10秒钟内找出着陆地点，否则火箭将偏离方向。另一方面，简单查找算法编写起来更容易，因此出现bug的可能性更小。小明可不希望引导火箭着陆的代码中有bug！为确保万无一失，小明决定计算两种算法在列表包含100个元素的情况下需要的时间。
> 
> 假设检查一个元素需要1毫秒。使用简单查找时，小明必须检查100个元素，因此需要100毫秒才能查找完毕。而使用二分查找时，只需检查7个元素（log2100 大约为7），因此需要7毫秒就能查找完毕。

![bafcc0ff7b7335d0d6ad632cb8b86911.png][]

> 然而，实际要查找的列表可能包含10亿个元素，在这种情况下，简单查找需要多长时间呢？二分查找又需要多长时间呢？请务必找出这两个问题的答案，再继续。
> 
> 使用包含10亿个元素的列表运行二分查找，运行时间为30毫秒（log21 000 000 000大约为30）。小明心里想，二分查找的速度大约为简单查找的15倍，因为列表包含100个元素时，简单查找需要100毫秒，而二分查找需要7毫秒。因此，列表包含10亿个元素时，简单查找需要30 × 15 = 450毫秒，完全符合在10秒内查找完毕的要求。小明决定使用简单查找。这是正确的选择吗？
> 
> 不是。实际上，小明错了，而且错得离谱。列表包含10亿个元素时，简单查找需要10亿毫秒，相当于11天！为什么会这样呢？因为二分查找和简单查找的运行时间的增速不同。

![4c7add0a032cee7f349c2dee02630cb9.png][]

> 也就是说，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。Bob以为二分查找速度为简单查找的15倍，这不对：列表包含10亿个元素时，为3300万倍。

>  **有鉴于此，仅知道****算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。****这正是大O表示法的用武之地。**

> 大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，**它指出了算法运行时间的增速**。

> 再来看一个例子。为检查长度为n的列表，二分查找需要执行log2n 次操作。使用大O表示法，这个运行时间怎么表示呢？O(log2n)。一般而言，大O表示法像下面这样。

![95bc429a693d098bab115e40a7a1a499.png][]

> 这指出了算法需要执行的操作数。之所以称为大O表示法，是因为操作数前有个大O。这听起来像笑话，但事实如此！

--------------------

## 三. 总结 ##

> 有了基本操作执行次数的函数T(n)，无法直接分析和比较代码的运行时间。
> 
> 例如算法A的执行次数是T(n)= 100n，算法B的执行次数是T(n)= 5n2，这两个函数到底谁的运行时间更长一些，需要看n的取值。
> 
> 因此，大O表示法就是把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n2、n3等。

--------------------

## 五. 扩展 ##

[算法分析——大O标记法之时间复杂度][O]；

[算法分析——大O标记法之空间复杂度][O 1]；

[d5e2b8d772ba3b346168605da0c7982c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0b6fecb8d30c48b8b87793de6d5f75c5.png
[bafcc0ff7b7335d0d6ad632cb8b86911.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1780c3dc55fe4b5e976e238667ce2e92.png
[4c7add0a032cee7f349c2dee02630cb9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4cfc04c2ad3140a4b6106a0e4d13761f.png
[95bc429a693d098bab115e40a7a1a499.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d93f84582081484aac3e358bcae66777.png
[O]: https://blog.csdn.net/weixin_53919192/article/details/126329582?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22126329582%22%2C%22source%22%3A%22weixin_53919192%22%7D
[O 1]: https://blog.csdn.net/weixin_53919192/article/details/126331533?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22126331533%22%2C%22source%22%3A%22weixin_53919192%22%7D