专栏首页代码随想录究竟什么是时间复杂度,怎么求时间复杂度,看这一篇就够了

究竟什么是时间复杂度,怎么求时间复杂度,看这一篇就够了

关于代码的一切尽在「代码随想录」

究竟什么是时间复杂度

时间复杂度就是用来方便开发者估算出程序的运行时间

我们该如何估计程序运行时间呢,我们通常会估计算法的操作单元数量,来代表程序消耗的时间, 这里我们默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n,那么操作单元数量便用函数f(n)来表示

随着数据规模n的增大,算法执行时间的增长率和f(n)的增长率相同,这称作为算法的渐近时间复杂度,简称时间复杂度,记为 O(f(n))

什么是大O

这里就要说一下这个大O,什么是大O呢,很多同学说时间复杂度的时候都知道O(n),O(n^2),但说不清什么是大O

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

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

但是在数据本来有序的情况下时间复杂度是O(n),也就对于所有输入情况来说,最坏是O(n^2) 的时间复杂度,所以称插入排序的时间复杂度为O(n^2)

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

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

所以这里大家知道这么一回事就好了

面试中面试官绝对不会针对快速排序的时间复杂度问题来讨论O的定义, 大家知道讨论的时间复杂度就是指一般情况下的时间复杂度就好了。

大家要对算法的时间复杂度有这样的一个概念

就是同一个算法的时间复杂度不是一成不变的,和输入的数据形式依然有关系

我们主要关心的还是一般情况下的数据形式。

面试中说道算法的时间复杂度是多少指的都是一般情况

但是如果面试官和我们深入探讨一个算法的实现以及性能的时候 我们就要时刻想着 数据用例的不一样 时间复杂度也是不同的,这一点同学们要注意

如何描述时间复杂度

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

我们在决定使用那些算法的时候 ,不是时间复杂越低的越好,要考虑数据规模,如果数据规模很小 甚至可以用O(n^2)的算法比 O(n)的更合适

就像上图中图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的,所花费的时间也是最少的。

那我们为什么在计算时间复杂度的时候要忽略常数项系数呢,也就说O(100n) 就是O(n)的时间复杂度,O(5n^2) 就是O(n^2)的时间复杂度

而且要默认O(n) 优于O(n^2) 呢 ?

这里就又涉及到大O的定义

因为大O其实就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度,这个点也就是 常数项系数已经不起决定性作用的点。

例如上图中 20 就是那个点 ,n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的,是因为一般情况下我们都是默认数据规模足够的大,基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示:

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

你所不知道的O(logn)

我们平时说这个算法的时间复杂度是logn的,一定是log 以2为底n的对数么?

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

为什么可以这么做呢?

如下图所示

假如我们有两个算法的时间复杂度 分别是log以2为底n的对数 和 log 以10为底n的对数

那么这里如果大家还记得我们高中数学的话,应该不能理解 以2为底n的对数 = 以2为底10的对数 乘以 以10为底n的对数

那这里以2为底10的对数 是一个常数,而我在上面已经讲述了我们计算时间复杂度是忽略常数项系数的

抽象一下 log 以i为底n的对数 等于 log 以j为底n的对数,所以我们忽略了i,直接说是logn,正式因为logij 是就一个常数

所以,这样就应该不难理解了 我们为什么忽略底数了

如果时间复杂度是一个复杂的表达式,我们如何简化

有时候,我们去计算时间复杂度的时候 发现不是一个 简单的O(n) 或者O(n^2), 而是一个复杂的表达式,例如:

O(2*n^2 + 10*n + 1000)

那这里我们通常如何描述这个算法的时间复杂度呢,一种方法就是简化法

去掉运行时间中的加法常数项 (因为常数项并不会因为n的增大而增加计算机的操作次数)

O(2*n^2 + 10*n)

去掉常数系数 (我们刚刚已经详细讲过为什么可以去掉常数项的原因了)

O(n^2 + n)

只保留保留最高项 去掉数量级小一级的n (因为n^2 的数据规模远大于 n),最终简化为:

O(n^2)

如果这一步同学们理解有困难,那也可以做提取n的操作,变成O(n(n+1)) ,省略加法常数项后 也别变成了

O(n^2)

所以最后我们说:我们这个算法的算法时间复杂度是 O(n^2)

也可以用另一种简化的思路,当n大于40的时候 , 这个复杂度 会一直小于O(3*n^2)

O(2*n^2 + 10*n + 1000) < O(3*n^2)

所以说 最后我们省略掉常数项系数最终时间复杂度也是O(n^2)

举例说明时间复杂度要怎么算

我们通过一道题目,来看一下具体时间复杂度应该怎么算

题目描述:找出n个字符串中相同的两个字符串(假设这里只有两个相同的字符串)

一些同学可能以为解决这道题目可以采用枚举遍历的解法,时间复杂度是O(n^2)

这个时间复杂度其实是不对的。

这里一些同学忽略了字符串比较的时间消耗,这里并不像int 型数字做比较那么简单

除了n^2 次的遍历次数外, 字符串比较依然要消耗m次操作(m也就是字母串的长度),所以时间复杂度是O(m*n*n)

那么我们再想一下其他解题思路

我们先排对n个字符串按字典序来排序,排序后n个字符串就是有序的,意味着两个相同的字符串就是挨在一起

然后在遍历一遍n个字符串,这样就找到两个相同的字符串了

那我们来看看这种算法的时间复杂度

快速排序时间复杂度 为O(nlogn),依然要考虑字符串的长度是m,那么快速排序每次的比较都要有m次的字符比较的操作,就是O(m*n*logn)

之后我们还要遍历一遍这n个字符串找出两个相同的字符串,别忘了遍历的时候依然要比较字符串,所以总共的时间复杂度是 O(m*n*logn + n*m)

我们对O(m*n*logn + n*m) 进行简化操作,把m*n提取出来变成O(m*n*(logn + 1))

在省略常数项最后的时间复杂度是 O(m*n*logn), 那我们比较一下时间效率O(m*n*logn) 是不是比第一种方法O(m*n*n)更快一些呢

很明显O(m*n*logn) 要优于O(m*n*n)

所以 先把字符串集合排序在遍历一遍找到两个相同字符串的方式要比直接暴力枚举的方式更快。

通过这个例子 希望大家对时间复杂的是怎么算的有一个初步的理解和认识。

本文分享自微信公众号 - 代码随想录(code_thinking),作者:代码随想录

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法分析中的空间复杂度,你真的会了么?

    空间复杂度是对一个算法在运行过程中占用内存空间大小的量度,记做S(n)=O(f(n))。

    代码随想录
  • 一场面试,带你彻底掌握递归算法的时间复杂度

    同一道题目,同样使用递归算法,有的同学写出了O(n)的代码,有的同学就写出了O(logn)的代码

    代码随想录
  • 栈与队列:匹配问题都是栈的强项

    给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

    代码随想录
  • 笔试常考题型之时间复杂度

    Zoctopus
  • 数据结构和算法

    10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    分母为零
  • 昨天的文章,有朋友给出"更好的"解法,其实并不是...

    昨天推送一道题目分析,一方面学习一个颇具特色的数组,它的取值不大于数组长度;另一方面通过这道题充分体会算法分析、逻辑推理的重要性。只有做好充分的分析,才可能写出...

    double
  • 读张逸的领域驱动设计之应对软件复杂度笔记 原

        Eric Evans认为"很多应用程序最主要的复杂度并不是技术上,而是来自域本身、用户的活动或业务"。最终决定的因素还是因为需求。

    克虏伯
  • 02 复杂度分析_pythoner学习数据结构与算法系列

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度...

    诡途
  • 数据结构算法入门--一文了解什么是复杂度

    最近会开始更新一个数据结构算法的学习系列,同时不定期更新 leetcode 的刷题。

    kbsc13
  • 算法笔记(八):复杂度分析(二)

    #感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

    free赖权华

扫码关注云+社区

领取腾讯云代金券