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

た入场券 2024-04-08 08:25 81阅读 0赞

> 大家可移步[算法分析——大O标记法][O]进行对大O标记法进行了解；

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

**目录**

一. 理解不同的大O 运行时间

算法1

算法2

二. 大O 表示法指出了最糟情况下的运行时间

三. 一些常见的大O 运行时间

四. 确定大O表示法的原则

4.1 示例说明

1）忽略常数项

2）忽略低次项

3）忽略系数

4.2 示例练习：

4.3 示例代码

五. 总结

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

## 一. 理解不同的大O 运行时间 ##

> 以一个你在家里使用纸和笔就能完成的实验来说明该问题。

> 假设你要画一个网格，它包含16个格子。

![0e8127cd805d8474a73f49bdb217b19c.png][]

### 算法1 ###

> 一种方法是以每次画一个的方式画16个格子。记住，大O表示法计算的是操作数。在这个示例中，画一个格子是一次操作，需要画16个格子。如果每次画一个格子，需要执行多少次操作呢？

![3ad94bc654d25bdec508f0eafe2f2ba3.png][]

> 画16个格子需要16步。这种算法的运行时间是多少？
> 
> **答案：**算法1的运行时间为O(n)；

### 算法2 ###

> 请尝试这种算法——将纸折起来。将纸对折一次就是一次操作。第一次对折相当于画了两个格子！再折，再折，再折。

![5f16187083103e23c00e2821ef29bfb7.png][]

> 折4次后再打开，便得到了漂亮的网格！每折一次，格子数就翻倍，折4次就能得到16个格子！

> 你每折一次，绘制出的格子数都翻倍，因此4步就能“绘制”出16个格子。这种算法的运行时间是多少呢？
> 
> **答案：**算法2的运行时间为O(log n)。

> 搞清楚这两种算法的运行时间之后，再继续。

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

## 二. 大O 表示法指出了最糟情况下的运行时间 ##

> 假设你使用简单查找在英文电话簿中找人。你知道，简单查找的运行时间为O(n)，这意味着在最糟情况下，必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人，一次就能找到，无需查看每个条目。考虑到一次就找到了Adit，请问这种算法的运行时间是O(n)还是O(1)呢？

> **简单查找的运行时间总是为O(n)。**

> 查找Adit时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

> 除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在后面讨论。

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

## 三. 一些常见的大O 运行时间 ##

> 下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
> 
>  *  O(log n)，也叫对数时间，这样的算法包括二分查找。
>  *  O(n)，也叫线性时间，这样的算法包括简单查找。
>  *  O(n \* log n)，这样的算法包括后面将介绍的快速排序——一种速度较快的排序算法。
>  *  O(n2)，这样的算法包括后面将介绍的选择排序——一种速度较慢的排序算法。
>  *  O(n!)，这样的算法包括后面将介绍的旅行商问题的解决方案——一种非常慢的算法。

![323f2f413b1c1d688771f8e202c2e2c4.png][]

> 以上面绘制网格实验为例，且假设有5种不同的算法可供选择，这些算法的运行时间如上所示。
> 
>  *  第一种算法，绘制该网格所需的操作数将为4（log 16 = 4）。假设你每秒可执行10次操作，那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢？这需要执行10（log 1024 = 10）次操作，换言之，绘制这样的网格需要1秒。
>  *  第二种算法，其运行时间为O(n)。即要绘制16个格子，需要执行16次操作；要绘制1024个格子，需要执行1024次操作。执行这些操作需要多少秒呢？
>  *  整体如下图：

![0693fcd144de9946d64d5b592a11fee4.png][]

> 还有其他的运行时间，但这5种是最常见的。
> 
> 这里做了简化，实际上，并不能如此干净利索地将大O运行时间转换为操作数，但就目前而言，这种准确度足够了。等继续学习其他一些算法后，将回过头来再次讨论大O表示法。当前，我们获得的主要启示如下：
> 
>  *  **算法的速度指的并非时间，而是操作数的增速。**
>  *  **谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。**
>  *  **算法的运行时间用大O表示法表示。**
>  *  **O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。**

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

## 四. 确定大O表示法的原则 ##

> 因此，大O表示法就是把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n2、n3等，原则如下：
> 
>  *  **如果运行时间是常数量级，则用常数1表示**
>  *  **只保留时间函数中的最高阶项**
>  *  **如果最高阶项存在，则省去最高阶项前面的系数**

### 4.1 示例说明 ###

#### 1）忽略常数项 ####

> 函数如下表：

> 函数增长图为：

![9764effea73cfe2f8ded6dd53038f0a5.png][]

>  **结论:**
> 
>  *  2n+20和 2n 随着n 变大，执行曲线无限接近, 20可以忽略
>  *  3n+10和 3n 随着n 变大，执行曲线无限接近, 10可以忽略

#### 2）忽略低次项 ####

> 函数如下表：

> 函数增长图为：

![9abf84423a7693a7c9e85b76b28fad44.png][]

>  **结论:**
> 
>  *  2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
>  *  n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20

#### 3）忽略系数 ####

> 函数如下表：

> 函数增长图为：

![1872df6b35e5561306f2933bf71ab350.png][]

>  **结论:**
> 
>  *  随着n值变大，5n^2+7n和 3n^2 + 2n ，执行曲线重合, 说明这种情况下, 5和3可以忽略
>  *  而n^3+5n和 6n^3+4n，执行曲线分离，说明多少次方是关键

### 4.2 示例练习： ###

1) T(n) = 3n

T(n) = 3n
    最高阶项为3n，省去系数3，则转化的时间复杂度为：T(n)=O(n)

![6d293c36e5b72ba13de4ed5d4031b5ab.png][]

2) T(n) = 5logn

T(n) = 5logn，
    最高阶项为5logn，省去系数5，则转化的时间复杂度为：T(n) =O(logn)。

![a47149157e36c33610fc1451212f5c87.png][]

3) T(n) = 2

T(n) = 2，
    只有常数量级，则转化的时间复杂度为：T(n) =O(1)。

![1bf903eccaf3b166700f96fdd76d626d.png][]

4) T(n) = 0.5n2+ 0.5n

T(n) = 0.5n^2+ 0.5n，
    最高阶项为0.5n^2，省去系数0.5，则转化的时间复杂度为：T(n) =O(n^2)。

![7634ff44d712ee4827f81aa601588f60.png][]

> 这4种时间复杂度究竟谁的程度执行用时更长，谁更节省时间呢？当n的取值足够大时，不难得出下面的结论：
> 
> **O(1)<O(logn)<O(n)<O(n2****)**

### **4.3** 示例代码 ###

> 举一个例子，来说明前面的大O表示法：

public static int sum(int n) {
 int partialSum = 0;
 for(int i=1;i<=n;i++) {
 partialSum += i*i*i;
 }
 return partialSum;
 }

> 程序分析如下：
> 
> * 第2行和第6行各占一个时间单元
> * 第3行在初始化i，比较i<=n，对i进行自增运算，共2N+2个时间单元
> * 第4行在循环中，每执行一次占用4个时间单元（两次乘法，一次加法，一次赋值），共执行N次占用4N个时间单元
> * 因此在忽略调用方法和返回值开销情况下，方法总计占用 **6N+4** 个时间单元，是“线性增长”
> * **结论：该方法是 O( n )**

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

## 五. 总结 ##

>  *  二分查找的速度比简单查找快得多。
>  *  O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
>  *  算法运行时间并不以秒为单位。
>  *  算法运行时间是从其增速的角度度量的。
>  *  算法运行时间用大O表示法表示。

[O]: https://blog.csdn.net/weixin_53919192/article/details/126329470?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22126329470%22%2C%22source%22%3A%22weixin_53919192%22%7D
[0e8127cd805d8474a73f49bdb217b19c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2995fd438df748aeb3c9b7dbbfe22fc6.png
[3ad94bc654d25bdec508f0eafe2f2ba3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/343c693c0af84b4faa677f1c19d482cf.png
[5f16187083103e23c00e2821ef29bfb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e36645b9245044d185dd38792e46bd28.png
[323f2f413b1c1d688771f8e202c2e2c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/f6ad5dc6a12e427896e57be49645843e.png
[0693fcd144de9946d64d5b592a11fee4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1822b80b8a834219887d96d483617550.png
[9764effea73cfe2f8ded6dd53038f0a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/411a1f81f0c249129a52e42b4d680f25.png
[9abf84423a7693a7c9e85b76b28fad44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/03cb503198344db5a38cbdca54d711cf.png
[1872df6b35e5561306f2933bf71ab350.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c8ebd4fa1efc4d8d8b65e5c6277d2d0b.png
[6d293c36e5b72ba13de4ed5d4031b5ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/713f09a2d60242c5a407eac08e5844a7.png
[a47149157e36c33610fc1451212f5c87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2696c688402843729ef5776da80c75fe.png
[1bf903eccaf3b166700f96fdd76d626d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/a1949b027c6045e7a10813bf32d9db9c.png
[7634ff44d712ee4827f81aa601588f60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e7b5bb1d7d2844548001a8c519ef5af5.png