初学算法的小菜鸡 - 自学笔记 (第一天): 算法的评估标准 时间复杂度

本文主要是介绍初学算法的小菜鸡 - 自学笔记 (第一天): 算法的评估标准 时间复杂度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文的博主也就是本人也算是根正苗红的计算机科学专业，从进入大学开始就一直对算法耳濡目染但从未认真研究及学习。时至今日尽管已经能够独立完成一些项目，但仍觉与正规军相差甚远。其根本原因可能就是基本功不够扎实，于是决心从今日起潜心算法，日日更新。

本笔记的内容来自对网络资料，书籍或者其他博客的总结及个人化(用自己的话再白话一遍)，笔记的主要学习规划线路参考Carl大神的代码随想录，这也是在我苦心搜集和寻找之后觉得能够让我从基础开始跟随的最优选择。本人算法小白，如有大佬路过请轻喷。

从如下六点进行分析：

• 究竟什么是时间复杂度

’条条大路通罗马‘，编程也是一样，实现同一功能的写法可以有多种，但是如何评判哪一种是更好的呢？时间复杂度便是评判标准之一。时间复杂度简而言之就是你写出来的程序运行时间效率的估算方式。为什么是估算呢？

为便于计算时间复杂度，通常会估计算法的操作单元数量 (不需要明确的计算出算法执行所需要的确切的操作单元数量，我们评估时了解大概趋势即可)，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。

简化的公式表示： 总运行时间 = 操作次数 * 固定时间的运行单元

节选自张云飞VIR

这里博主认为编写的算法的运行时间不仅仅受算法结构和质量本身的影响，也会受到计算机硬件性能的影响。因此不同计算机上相同结构和质量的算法也有可能具有不同的运行时间 (即运行单元的运行时间在不同的硬件上可能不同)。因此使用函数形式对于运行时间进行估算，统一相同算法在不同计算机上的运行时间效率是很有必要的。

通常来说我们可以把估算计算过程的大概趋势抽象成四种类型，能够对应四种不同场景：

以下场景例子参考: 一套图 搞懂“时间复杂度”

线性类型

场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？

答案自然是 3 X 10 = 30天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 3 X n = 3n 天。

如果用一个函数来表达这个相对时间，可以记作 T（n） = 3n。

对数类型

场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？

这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2位底，16的对数，可以简写为log16。

因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。

如果面包的长度是 N 寸呢？

需要 5 X logn = 5logn天，记作 T（n） = 5logn。

常数类型

场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？

答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。

如果面包的长度是 N 寸呢？

无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2。

平方类型

场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？

答案是从1累加到10的总和，也就是55天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。

记作 T（n） = 0.5n^2 + 0.5n。

事实上场景中的n就是我们之前所提到的操作单元数量即公式中的操作次数。经过上面的四个场景的介绍，大概已经清楚算法的执行方式大体上就上述的四种场景，因此我们可以用这四种类型的公式来对时间复杂度进行抽象的估算。

• 什么是大O

通常来说，我们期望“操作次数”是一个常数，而实际它很难直接用常数表示。于是引入了 渐进时间复杂度,官方的定义如下:

渐进时间复杂度（Asymptotic Time Complexity）：
若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

 节选自张云飞VIR

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

对于这个渐进时间复杂度的定义其实很好理解，T（n）/ f（n）的极限值为不等于零的常数，证明了T (n)和f (n)这两个函数的值的变化速度是同一个数量级的 (同阶函数，为1是等价函数)，若T (n)的变化速度远大于或远小于f (n)则T（n）/ f（n）的极限值应为无穷或0 (大家可以去看下对于判断两个函数的高阶，低阶，同阶和等价的概念)。

既然函数同阶那么我们就可以利用这个同阶的函数来代表这一类问题的时间复杂度，即统一时间效率的评估标准（反正我们也不需要算出确切的时间，都是在进行估算）。

推导出时间复杂度呢？有如下几个原则：

(1) 如果运行时间是常数量级，用常数1表示；
(2) 只保留时间函数中的最高阶项；
(3) 如果最高阶项存在，则省去最高阶项前面的系数。

场景1：
T(n) = 1
最高阶项为3n，省去系数3，转化后为：T(n) = O(1)

场景2：
T(n) = 5logn
最高阶项为5logn，省去系数5，转化后为：T(n) = O(logn)

场景3：
T(n) = 3n
最高阶项为3n，省去系数3，转化后为：T(n) = O(n)

场景4：
T(n) = 0.5n^2 + 0.5n
最高阶项为0.5n^2，省去系数0.5，转化后为：T(n) = O(n^2)
备注：^ 符号表示 平方，n^2表示 n的平方

这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：

O(1)< O(logn)< O(n)< O(n^2)

其实这四种对应的时间复杂度是： 常数阶，对数阶，线性阶，立方阶。

常见时间复杂度还有:常数阶、线性阶、平方阶、立方阶、对数阶、nlogn阶、指数阶：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

节选自张云飞VIR

Carl大神对于大O的另一个说明是目前我们常说的时间复杂度是指算法在一般情况下的时间效率：

算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2) 。

输入数据的形式对程序运算时间是有很大影响的，在数据本来有序的情况下时间复杂度是O(n)，但如果数据是逆序的话，插入排序的时间复杂度就是O(n^2)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

同样的同理再看一下快速排序，都知道快速排序是O(nlog n)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2)的，所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)。

但是我们依然说快速排序是O(nlog n)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。

 

• 不同数据规模的差异

事实上上述的情况都是在考虑数据量趋近于无穷的情况下，Carl大神给出了不理想情况即不同数据规模下的一些差异。

如下图中可以看出不同算法的时间复杂度在不同数据输入规模下的差异。

在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等），要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适（在有常数项的时候）。

面试中说道算法的时间复杂度是多少指的都是一般情况。但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。

• 复杂表达式的化简

有如下几个原则，刚才博主有提到实际上是一样的，这边看不懂可以回看刚刚的场景示例：

(1) 如果运行时间是常数量级，用常数1表示；
(2) 只保留时间函数中的最高阶项；
(3) 如果最高阶项存在，则省去最高阶项前面的系数。

• 中的log是以什么为底

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

这篇关于初学算法的小菜鸡 - 自学笔记 (第一天): 算法的评估标准 时间复杂度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！