时间复杂度和空间复杂度

一. 前言

1. 思考

算法，即解决问题的方法。同一个问题，使用不同的算法，虽然得到的结果相同，但是耗费的时间和资源是不同的。就比如要拧一个螺母，使用扳手还是钳子是有区别的，虽然使用钳子也能拧螺母，但是没有扳手好用。“条条大路通罗马”，解决问题的算法有多种，这就需要判断哪个算法“更好”。

2. 算法 vs 程序

很多人认为，程序就是算法，其实不然。 算法是解决某个问题的想法和思路；而程序则是把想法和思路用代码实现出来并且可以运行。算法可以是伪代码，程序则是实实在在的可以运行的代码。

比如：我们想把一个数组的中的值输出来，首先想到的是通过 for 循环，这就是算法；在这个想法的基础上通过代码编写程序。

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

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

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

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

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

4. 好算法的标准

(1). 对于一个算法而言，首先它得必须能解决这个问题(称为准确性)，其次通过该算法编写的程序必须要在任何情况下都不崩溃（称为健壮性）。

(2). 在满足了算法满足了 准确性 和 健壮性后，接下来要考虑的就是通过该算法编写的程序的运行效率如何，运行效率主要体现在两个方面：

A. 算法的运行时间。（称为：时间复杂度）

B. 运行算法所需的内存空间大小。(称为：空间复杂度)

调查表明：

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

二. 时间复杂度

1. 计算方式

计算一个算法的时间复杂度，不能把该算法全部用代码实现然后在电脑上跑，会做很多无用功，实际采用的方法都是估算。

程序一般由三种结构组成，分别是：顺序结构、分支结构、循环结构。顺序和分支结构中的每段代码只运行一次，而循环结构要看循环的次数。

由于是估算时间复杂度，循环结构对执行时间影响最大，所有算法的时间复杂度，主要是看算法中使用到的循环次数 (称为"频度")。次数越少，算法的时间复杂度越低。

例如：

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.

2. 表示方式

(1). 采用大 O 计法，即：O(频度)；对于上边的例子，a 的时间复杂度为 O(1)，b 的时间复杂度为 O(n)，c 的时间复杂度为 O(n2)。

(2). 如何简化？

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

简化三步走：

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

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

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

所以最终 a，b，c 合并后代码的时间复杂度为：O(n2)

更多 C++后台开发技术点知识内容包括 C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，MongoDB，ZK，流媒体，音视频开发，Linux 内核，TCP/IP，协程，DPDK 多个高级知识点。

C/C++Linux服务器开发高级架构师/C++后台开发架构师免费学习地址

【文章福利】另外还整理一些C++后台开发架构师 相关学习资料，面试题，教学视频，以及学习路线图，免费分享有需要的可以点击领取

3. 时间复杂度的类型和排序

常见的几种时间复杂度，由小到大排列：O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

4. 练习

       //时间复杂度为 O(1)        public int Cal1(int n)        {            var sum = n;                       return sum;        }
        //时间复杂度为 O(n)        public int Cal2(int n)        {            var sum = 0;            for (int i = 0; i < n; i++)            {                sum += i;            }            return sum;        }
        //由两个数据规模决定，所以时间复杂度为O(m+n)        public int Cal3(int m,int n)        {            var sum = 0;            for (int i = 0; i < m; i++)            {                sum += i;            }            for (int j = 0; j < n; j++)            {                sum += j;            }            return sum;        }
        //时间复杂度为：O(n2)平方阶        public int Cal4(int m, int n)        {            var sum1 = 0;
            for (int i = 0; i < m; i++)            {                for (int j = 0; j < n; j++)                {                    sum1 += i*j;                }            }                   return sum1;        }

三. 时间--空间 互换

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

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

(2). 算法中，例如判断某个年份是否为闰年时，

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

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

原文链接：第一节：时间复杂度和空间复杂度 - Yaopengfei - 博客园