专栏首页AI机器学习与深度学习算法数据结构与算法 1-4 常见时间复杂度与大小关系

数据结构与算法 1-4 常见时间复杂度与大小关系

本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

最常见的时间复杂度

上面表格中分为三列:

  1. 执行次数函数举例。就是前几个小节分析的F(n)函数,F(n)是关于问题规模和执行总的基本操作数的函数;
  2. 阶。就是时间复杂度T(n)。对应着就是F(n)去掉次要项以及常数项后的g(n)函数,此时称g(n)为F(n)的渐进函数,然后通过大O记法来表示时间复杂度T(n),此时T(n) = O(g(n));
  3. 非正式术语。由于我们不关心基本操作数的细节,只关心数量级和趋势,因此虽然不同算法的F(n)可能不同,但是通过大O记法的时间复杂度总归是那么几种情况,因此相应的为这几种情况进行一个非正式的命名。

下面以执行基本操作总数3n^2 + 2n + 1,即F(n) = 3n^2 + 2n + 1为例,来详细说明一下计算时间复杂度的大致过程。其实要想求时间复杂度只需要记住上一小节提到的6个基本计算规则即可:

  1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
  2. 顺序结构,时间复杂度按加法进行计算
  3. 循环结构,时间复杂度按乘法进行计算
  4. 分支结构,时间复杂度取最大值
  5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
  6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

1-4是用于计算算法的总的基本操作说F(n),5,6是求解时间复杂度相关的计算规则。

此时已知了基本操作总数F(n),因此1-4条基本计算规则用不到了。3n^2 + 2n + 1按照5的计算规则,只关心基本操作数的最高次项,去掉其他次要项以及常数项,因为我们只关心数量级和趋势,可以看出3n^2 + 2n + 1的趋势是有n^2所主导的,所以把n作为次要项,然后去掉其余的常数项,最终得到的g(n) = n^2,时间复杂度T(n) = O(g(n)) = O(n^2)。

常见时间复杂度之间大小关系

根据上图可以看出这些常见时间复杂度的大小关系,需要记住下面的大小关系:

下面简单举几个例子,左边部分是O里面是算法执行的总的基本操作数,通过大O记法变成右边时间复杂度的形式。

  1. O(5) ==> O(1)
  2. O(2n + 1) ==> O(n)
  3. O(n^2 + n + 1) ==> O(n^2)
  4. O(3n^3 + 1) ==> O(n^3)

根据常见时间复杂度的大小关系可以得出上面4个时间复杂度所耗时间大小关系:O(n^3) > O(n^2) > O(n) > O(1),也就是算法的效率。

本文分享自微信公众号 - AI机器学习与深度学习算法(AI-KangChen),作者:Chenkc

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

原始发表时间:2019-07-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法 1-3 最坏时间复杂度与计算规则

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍算法时间复杂度的三种不同程度:最坏时间复杂度、最优时间复杂度以及平均时间复杂度,并且介绍...

    触摸壹缕阳光
  • 数据结构与算法 1-7 Python列表与字典操作的时间复杂度

    触摸壹缕阳光
  • [L3]Seq2Seq中Beam search算法

    由于在公众号上文本字数太长可能会影响阅读体验,因此过于长的文章,我会使用"[L1]"来进行分段。这系列将介绍Seq2Seq模型中的Beam Search算法。

    触摸壹缕阳光
  • 常用算法解析

    算法基础:概念,时间复杂度,空间复杂度,常见算法以及复杂度计算 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

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

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

    double
  • 数据结构和算法

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

    分母为零
  • 数据结构算法入门--一文了解什么是复杂度

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

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

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

    克虏伯
  • 数据结构与算法学习笔记之 复杂度分析

    大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜...

    Dawnzhang
  • 笔试常考题型之时间复杂度

    Zoctopus

扫码关注云+社区

领取腾讯云代金券