【编程大法】算法的时间复杂度和空间复杂度！

梦里梦外; 2023-01-13 15:52 57阅读 0赞

算法，即解决问题的方法。同一个问题，使用不同的算法，虽然得到的结果相同，但是耗费的时间和资源是不同的。

就比如要拧一个螺母，使用扳手还是钳子是有区别的，虽然使用钳子也能拧螺母，但是没有扳手好用。

“条条大路通罗马”，解决问题的算法有多种，这就需要判断哪个算法“更好”。

### 算法VS程序 ###

很多人误以为程序就是算法，其实不然：算法是解决某个问题的想法、思路；而程序是在心中有算法的前提下编写出来的可以运行的代码。

> 例如，要解决依次输出一维数组中的数据元素的值的问题，首先想到的是使用循环结构（ for 或者 while ），在有这个算法的基础上，开始编写程序。

所以，**算法相当于是程序的雏形**。当解决问题时，首先心中要有解决问题的算法，围绕算法编写出程序代码。

### 有算法一定能解决问题吗？ ###

对于一个问题，想出解决的算法，不一定就能解决这个问题。

例如拧螺母，扳手相对于钳子来说更好使（选择算法的过程），但是在拧的过程（编写程序的过程）中发现螺母生锈拧不动，这时就需要另想办法。

为了避免这种情况的发生，要充分全面地思考问题，尽可能地考虑到所有地可能情况，慎重选择算法（需要在实践中不断地积累经验）。

### “好”算法的标准 ###

对于一个问题的算法来说，之所以称之为算法，首先它必须能够解决这个问题（称为准确性）。其次，通过这个算法编写的程序要求在任何情况下不能崩溃（称为健壮性）。

如果准确性和健壮性都满足，接下来，就要考虑最重要的一点：通过算法编写的程序，运行的效率怎么样。

**运行效率体现在两方面：**

✿ 算法的运行时间。（称为“时间复杂度”）

✿ 运行算法所需的内存空间大小。（称为“空间复杂度”）

好算法的标准就是：**在符合算法本身的要求的基础上，使用算法编写的程序运行的时间短，运行过程中占用的内存空间少，就可以称这个算法是“好算法”。**

> 调查表明，人们对于软件或者 APP 的运行效率有极高的要求，例如对于网页打开的忍耐极限是 6 秒甚至更短，如果你设计的网页打开的时间超过 6 秒，多数人会在 4 秒甚至 3 秒的时候毫不犹豫地关掉而去浏览其他网页。在这个大背景下，一个好的“算法”更注重的是时间复杂度，而空间复杂度只要在一个合理的范围内就可以。

### 时间复杂度的计算 ###

计算一个算法的时间复杂度，不可能把所有的算法都编写出实际的程序出来让计算机跑，这样会做很多无用功，效率太低。实际采用的方法是估算算法的时间复杂度。

在学习C语言的时候讲过，程序由三种结构构成：顺序结构、分支结构和循环结构。顺序结构和分支结构中的每段代码只运行一次；循环结构中的代码的运行时间要看循环的次数。

由于是估算算法的时间复杂度，相比而言，循环结构对算法的执行时间影响更大。所以，算法的时间复杂度，主要看算法中使用到的循环结构中代码循环的次数（称为“频度”）。次数越少，算法的时间复杂度越低。

**例如：**

a) ++x; s=0;

b) for (int i=1; i<=n; i++) \{ ++x; s+=x; \}

c) for (int i=1; i<=n; i++) \{ for (int j=1; i<=n; j++) \{ ++x; s+=x; \} \}

上边这个例子中，a 代码的运行了 1 次，b 代码的运行了 n 次，c 代码运行了 n\*n 次。

### 时间复杂度的表示 ###

算法的时间复杂度的表示方式为：

> O(频度)

这种表示方式称为大“O”记法。

> 注意，是大写的字母O，不是数字0。

对于上边的例子而言，a 的时间复杂度为O(1)，b 的时间复杂度为O(n)，c 的时间复杂度为为O(n2)。

如果a、b、c组成一段程序，那么算法的时间复杂度为 O(n2+n+1) 。但这么表示是不对的，还需要对 n2+n+1 进行简化。

简化的过程总结为3步：

✿ 去掉运行时间中的所有加法常数。（例如 n2+n+1，直接变为 n2+n）

✿ 只保留最高项。（n2+n 变成 n2）

✿ 如果最高项存在但是系数不是1，去掉系数。（n2 系数为 1）

所以，最终a、b和c合并而成的代码的时间复杂度为O(n2)。

### 常用的时间复杂度的排序 ###

列举了几种常见的算法时间复杂度的比较（又小到大）：

![9a6a5f14b9968b05554b7c4b790d90a4.png][]

### 拿时间换空间，用空间换时间 ###

算法的时间复杂度和空间复杂度是可以相互转化的。

谷歌浏览器相比于其他的浏览器，运行速度要快。是因为它占用了更多的内存空间，以空间换取了时间。

算法中，例如判断某个年份是否为闰年时，如果想以时间换取空间，算法思路就是：当给定一个年份时，判断该年份是否能被4或者400整除，如果可以，就是闰年。

如果想以空间换时间的话，判断闰年的思路就是：把所有的年份先判断出来，存储在数组中（年份和数组下标对应），如果是闰年，数组值是1，否则是0；当需要判断某年是否为闰年时，直接看对应的数组值是1还是0，不用计算就可以马上知道。

![fc2477a01039694a7c8e0d1028f7a6a7.gif][]

不管你是转行也好，初学也罢，进阶也可，如果你想学编程，进阶程序员~

【值得关注】我的 **[编程学习交流俱乐部][Link 1] **！【点击进入】

**C语言入门资料：**

![6b498990e77e868149a4b87438a21f1d.png][]

**C语言必读书籍：**

![2424460e8a4d3e70ea3639d13a8a166c.png][]

[9a6a5f14b9968b05554b7c4b790d90a4.png]: /images/20221022/a512d436195e4010abad15d4f17eb894.png
[fc2477a01039694a7c8e0d1028f7a6a7.gif]: /images/20221022/490adc535e1d4acc857628916880e97b.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=RS0PvN8j
[6b498990e77e868149a4b87438a21f1d.png]: /images/20221022/a0c3672c9d414a2a878f59b97595133b.png
[2424460e8a4d3e70ea3639d13a8a166c.png]: /images/20221022/5fa4940646d547b290f445a0881cdcc0.png