学习
实践
活动
专区
工具
TVP
写文章
专栏首页丑胖侠LeetCode0:学习算法必备知识:时间复杂度与空间复杂度的计算

LeetCode0:学习算法必备知识:时间复杂度与空间复杂度的计算

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项,也是每个高级程序员的必备技能。针对同一问题,可以有很多种算法来解决,但不同的算法在效率和占用存储空间上的区别可能会很大。

那么,通过什么指标来衡量算法的优劣呢?其中,上面提到的效率可以用算法的时间复杂度来描述,而所占用的存储空间可以用算法的空间复杂度来描述。

  • 时间复杂度:用于评估执行程序所消耗的时间,可以估算出程序对处理器的使用程度。
  • 空间复杂度:用于评估执行程序所占用的内存空间,可以估算出程序对计算机内存的使用程度。

在实践中或面试中,我们不仅要能够写出具体的算法来,还要了解算法的时间复杂度和空间复杂度,这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时,还需要从中选取一个平衡点。

一个算法通常存在最好、平均、最坏三种情况,我们一般关注的是最坏情况。最坏情况是算法运行时间的上界,对于某些算法来说,最坏情况出现的比较频繁,也意味着平均情况和最坏情况一样差。

通常,时间复杂度要比空间复杂度更容易出问题,更多研究的是时间复杂度,面试中如果没有特殊说明,讲的也是时间复杂度。

时间复杂度

要获得算法的时间复杂度,最直观的想法是把算法程序运行一遍,自然可以获得。但实践中往往受限于测试环境、数据规模等因素,直接测试算法要么难以实现,要么误差较大,而且理论上也没必要对每个算法都进行一遍测试,只需要找到一种评估指标,获得算法执行所消耗时间的基本趋势即可。

时间频度

通常,一个算法所花费的时间与代码语句执行的次数成正比,算法执行语句越多,消耗的时间也就越多。我们把一个算法中的语句执行次数称为时间频度,记作T(n)。

渐进时间复杂度

在时间频度T(n)中,n代表着问题的规模,当n不断变化时,T(n)也会不断地随之变化。那么,如果我们想知道T(n)随着n变化时会呈现出什么样的规律,那么就需要引入时间复杂度的概念。

一般情况下,算法基本操作的重复执行次数为问题规模n的某个函数,也就是用时间频度T(n)表示。如果存在某个函数f(n),使得当n趋于无穷大时,T(n)/f(n)的极限值是不为零的常数,那么f(n)是T(n)的同数量级函数,记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称为时间复杂度。

渐进时间复杂度用大写O表示,所以也称作大O表示法。算法的时间复杂度函数为:T(n)=O(f(n));

T(n)=O(f(n))表示存在一个常数C,使得在当n趋于正无穷时总有 T(n) ≤ C * f(n)。简单来说,就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T(n)的上界是C * f(n)。其虽然对f(n)没有规定,但是一般都是取尽可能简单的函数。

常见的时间复杂度有:O(1)常数型;O(log n)对数型,O(n)线性型,O(nlog n)线性对数型,O(n2)平方型,O(n3)立方型,O(nk)k次方型,O(2n)指数型。

上图为不同类型的函数的增长趋势图,随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log n)<Ο(n)<Ο(nlog n)<Ο(n2)<Ο(n3)<…<Ο(2^n)<Ο(n!)。

值得留意的是,算法复杂度只是描述算法的增长趋势,并不能说一个算法一定比另外一个算法高效。这要添加上问题规模n的范围,在一定问题规范范围之前某一算法比另外一算法高效,而过了一个阈值之后,情况可能就相反了,通过上图我们可以明显看到这一点。这也就是为什么我们在实践的过程中得出的结论可能上面算法的排序相反的原因。

如何推导时间复杂度

上面我们了解了时间复杂度的基本概念及表达式,那么实践中我们怎么样才能通过代码获得对应的表达式呢?这就涉及到求解算法复杂度。

求解算法复杂度一般分以下几个步骤:

  • 找出算法中的基本语句:算法中执行次数最多的语句就是基本语句,通常是最内层循环的循环体。
  • 计算基本语句的执行次数的数量级:只需计算基本语句执行次数的数量级,即只要保证函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,使注意力集中在最重要的一点上:增长率。
  • 用大Ο表示算法的时间性能:将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则:

  • 用常数1取代运行时间中的所有加法常数;
  • 只保留时间函数中的最高阶项;
  • 如果最高阶项存在,则省去最高阶项前面的系数;

下面通过具体的实例来说明以上的推断步骤和规则。

时间复杂度实例

常数阶O(1)

无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

int i = 1;
int j = 2;
int k = 1 + 2;

上述代码执行时,单个语句的频度均为1,不会随着问题规模n的变化而变化。因此,算法时间复杂度为常数阶,记作T(n)=O(1)。这里我们需要注意的是,即便上述代码有成千上万行,只要执行算法的时间不会随着问题规模n的增长而增长,那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。

对数阶O(log n)

先来看对应的示例代码:

int i = 1; // ①
while (i <= n) {
   i = i * 2; // ②
}

在上述代码中,语句①的频度为1,可以忽略不计。

语句②我们可以看到它是以2的倍数来逼近n,每次都乘以2。如果用公式表示就是122*2…*2 <=n,也就是说2的x次方小于等于n时会执行循环体,记作2^x <= n,于是得出x<=logn。也就是说上述循环在执行logn次之后,便结束了,因此上述代码的时间复杂度为O(log n)。

其实上面代码的时间复杂度公式如果精确的来讲应该是:T(n) = 1 + O(log n),但我们上面已经讲到对应的原则,“只保留时间函数中的最高阶项”,因此记作O(log n)。

线性阶O(n)

示例代码:

int j = 0; // ①
for (int i = 0; i < n; i++) { // ②
   j = i; // ③
   j++; // ④
}

上述代码中,语句①的频度为1,②的频度为n,③的频度为n-1,④的频度为n-1,因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1)来表示。进而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1,即O(n)=3n-1,去掉低次幂和系数即O(n)=n,因此T(n)=O(n)。

在上述代码中for循环中的代码会执行n遍,因此它消耗的时间是随着n的变化而成线性变化的,因此这类算法都可以用O(n)来表示时间复杂度。

线性对数阶O(nlogN)

示例代码:

for (int m = 1; m < n; m++) {
   int i = 1; // ①
   while (i <= n) {
      i = i * 2; // ②
   }
}

线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶,只不过在对数阶的外面套了一个n次的循环,当然,它的时间复杂度就是n*O(log n)了,于是记作O(nlog n)。

平方阶O(n²)

示例代码:

int k = 0;
for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
      k++;
   }
}

平方阶可对照线性阶来进行理解,我们知道线性阶是一层for循环,记作O(n),此时等于又嵌套了一层for循环,那么便是n * O(n),也就是O(n * n),即O(n^2)。

如果将外层循环中的n改为m,即:

int k = 0;
for (int i = 0; i < m; i++) {
   for (int j = 0; j < n; j++) {
      k++;
   }
}

那么,对应的时间复杂度便为:O(m * n)。

同理,立方阶O(n³)、K次方阶O(n^k),只不过是嵌套了3层循环、k层循环而已。

排序算法对比

上面介绍了各种示例算法的时间复杂度推理过程,对照上面的时间复杂度以及算法效率的大小,来看一下我们常见的针对排序的几种算法的时间复杂度对比。

空间复杂度

最后,我们再了解一下空间复杂度。空间复杂度主要指执行算法所需内存的大小,用于对程序运行过程中所需要的临时存储空间的度量,这里的空间复杂度同样是预估的。

程序执行除了需要存储空间、指令、常数、变量和输入数据外,还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括:指令空间(即代码空间)、数据空间(常量、简单变量)等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模,S(n)表示空间复杂度。

下面看两个常见的空间复杂度示例:空间复杂度O(1)和O(n)。

空间复杂度 O(1)

空间复杂度为O(1)的情况的示例代码与时间复杂度为O(1)的实例代码一致:

int i = 1;
int j = 2;
int k = 1 + 2;

上述代码中临时空间并不会随着n的变化而变化,因此空间复杂度为O(1)。总结一下就是:如果算法执行所需要的临时空间不随着某个变量n的大小而变化,此算法空间复杂度为一个常量,可表示为 O(1),即 S(n) = O(1)。

空间复杂度 O(n)

示例代码:

int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
   j = i;
   j++;
}

上述代码中,只有创建int数组分配空间时与n的大小有关,而for循环内没有再分配新的空间,因此,对应的空间复杂度为S(n) = O(n)。

总结一下

本篇文章给大家讲了可以通过时间复杂度和空间复杂度来衡量算法的优劣,同时用具体的实例来讲解如何计算不同方法的时间复杂度和空间复杂度。当我们了解了这些基本的概念、函数、计算方法、计算规则及算法性能之后,再进行算法的学习便可以轻松预估出算法的性能等指标。

参考文献:

https://blog.csdn.net/zolalad/article/details/11848739 https://zhuanlan.zhihu.com/p/50479555


本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:http://blog.csdn.net/wo541075754复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 算法的时间复杂度和空间复杂度计算

    在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是...

    全栈程序员站长
  • 算法的时间复杂度与空间复杂度

    时间复杂度和空间复杂度是用来评价算法效率高低的2个标准,身为开发者肯定会经常会听到这2个概念,但它们分别是什么意思呢?

    Umbrella1024
  • 【进阶之路】算法的时间复杂度与空间复杂度

    .markdown-body{word-break:break-word;line-height:1.75;font-weight:400;font-size:...

    南橘
  • 一文搞懂算法的时间复杂度与空间复杂度

    一 时间复杂度的概念   一般情况下,算法的基本操作重复执行的次数是模块n的某一函数f(n),因此,算法的时间复杂度记做 T(n) = O(f(n))。 随着模...

    深度学习思考者
  • 算法的时间与空间复杂度(一看就懂)

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有...

    奎哥
  • 创新!京东T7开创“新算法宝典”,图文并茂,全新演绎,太酷了

    算法是一门学问,但却总遭到一些程序员的冷落。现在的开发人员,更热衷于编程语言的修炼,以应付面试需求时的需要,所以对算法的学习,稍许忽略了些。实际上,近些年来,各...

    愿天堂没有BUG
  • 算法与数据结构(一):时间复杂度与空间复杂度

    最近突然萌生了一个想法,好好系统的学习一下算法与数据结构然后产生一系列的文章来回顾与总结学到的东西,这部分我想从最简单的部分一一介绍总结,包括一些很基础的内容 ...

    Masimaro
  • 数据结构与算法之基本概念

    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中...

    bigsai
  • So easy 10分钟搞懂时间复杂度和空间复杂度!

    温馨提醒: 本文适用于所有开发者人群、无论你是小白、初学者还是已经工作的"社会人"。

    IT学习日记
  • 分析时间与空间复杂度《三钻数据结构与算法笔记》

    学习任何一门知识的时候,我们需要分析清楚这门知识的核心是什么,从而在这个核心中我们可以得到什么。如果我们是盲目的吸收知识,其实很多知识我们都是在目前场景、工作、...

    三钻
  • 想学算法吗少年,跟我来吧

    伟大的编程领域的祖师爷尼古拉斯威茨提出程序=数据结构+算法,数据结构的重要性不言而喻,数据结构在计算机学习的过程中是一门必修课,考研一般也是数据结构必考,软件开...

    周杰伦本人
  • 数据结构与算法《一》

    互联网面试不管是电话面试还是现场面,少不了数据结构与算法,尤其大公司,徒手写算法题,是面试成功必备的技能。下面给出思维导图:

    伊泽瑞尔
  • 面试官系列 - LeetCode链表知识点&题型总结

    前段时间,写了面试必备的一系列文章,反应还不错。有一些读者反馈说,能不能整理一些面试常见的算法。前段时间,我恰好总结了 LeetCode 常见的面试算法题目。今...

    程序员徐公
  • 算法之旅:复杂度分析

    作为一个合格的技术人员,算法是必备知识。可以这么说,虽然不懂算法的人并不会失业,但如果你想快速晋升摆脱业务工程师CRUD的命运就一定离不开算法。同时不管是对于工...

    Rouse
  • 【化解数据结构】从这里开启数据结构和算法

    本专栏 【化解数据结构】,将在这里总结自己学习数据结构和算法的学习笔记,从这篇算法入门开始,未来更文将涉及栈、队列、链表、堆、树、图…等数据结构,以及经典排序算...

    小丞同学
  • 【趣学算法】Day1-为什么要学算法?

    14天阅读挑战赛 努力是为了不平庸~ 算法学习有些时候是枯燥的,这一次,让我们先人一步,趣学算法!

    跟着飞哥学编程
  • 【化解数据结构】从这里开启数据结构和算法

    本专栏 【化解数据结构】,将在这里总结自己学习数据结构和算法的学习笔记,从这篇算法入门开始,未来更文将涉及栈、队列、链表、堆、树、图…等数据结构,以及经典排序算...

    小丞同学
  • 到底什么才是真正的空间复杂度?

    现在有一个算法是这样的,给定一个数组,将数组中每个元素都乘以2返回,我实现了下面两种形式:

    彤哥

扫码关注腾讯云开发者

领取腾讯云代金券