专栏首页架构说吃土记:之前理解时间复杂度计算方式是错误的

吃土记:之前理解时间复杂度计算方式是错误的

问题还原

《算法导论》9.2:快速选择 时间复杂度是o(n),

这个认识不对呀,快速排序时间复杂度o(nlogn)都记忆多少次了

敲黑板:吃土记:之前理解时间复杂度计算方式是错误的。

查缺补漏

  • 时间复杂度 定义:

若有某个辅助函数f(n), 使得当n趋近于无穷大时,

敲黑板 T(n)/f(n)的极限值为不等于零的常数,

则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))

  • 根据定义,可以归纳出基本的计算步骤
  1. 计算出基本操作的执行次数T(n)
  2. 计算出T(n)的数量级
  3. 用大O来表示时间复杂度

O(n)

  • 代码
   a=0;
   b=1;                     ①
   for (i=1;i<=n;i++) ②
   {  
      s=a+b;    ③
      b=a;     ④  
      a=s;     ⑤
   }

   语句1的频度:1,        
   语句2的频度:n,        
   语句3的频度:n,        
   语句4的频度:n,    
   语句5的频度:n,
         T(n) = 1+4n
         f(n) = n
         lim(T(n)/f(n)) = 1*(1/n) + 4 = 4
        
         T(n) = O(n)

O(n2)

  • 代码
   for (i=1;i<n;i++)
   { 
       y=y+1;        ①   
       for (j=0;j<=(2*n);j++)    
          x++;        ②      
   }  

O(log2n)

method6(int n){
    while((n=n/2)>0){
        System.out.println("葵花宝典");
    }
}
/*
假如:n=8 ; 8/2=4 执行1次;4/2=2 执行1次;2/2=1 执行1次;1/2=0.5=0 执行判断后,不进入循环体。
    所以循环体执行3次,判断执行3+1次;2^3=8---->log2(8)=3
    n=16 ; 16/2=8 执行1次;8/2=4 执行1次;4/2=2 执行1次;2/2=1 执行1次;
    所以循环体执行4次,判断执行4+1次;2^4=16---->log2(16)=4

    所以时间复杂度:log2(n)+(log2(n)+1) = 2log2(n)+1
    log2(n):循环体内执行次数,(log2(n)+1):判断语句执行次数
*/

总结

用大O表示法如下:

method1: 1+1+1 = 3   即O(1)
method2: 1+(5+1)+5+5 = 17   即O(1)

method3: 3n+2   即O(n)

method4: 3n^2+4n+2   即O(n^2)
method5: 49n+2   即O(n)

method6: 2log2(n)+1   即O(logn)

method7: 2log5(n)+1   即O(logn)

method8: 2nlog2(n)+4log2(n)+2   即O(nlogn)

method9: 2n+2+4*((1/2)n^2+(1/2)n)+1   即O(n^2)

应用

堆排序中建堆过程的时间复杂度O(n)

其实,建堆的整个过程中一个节点的比较次数是与它的高度k成正比的,

所以,我们可以得出 第h层的元素有1个,它最多需要比较(h-1)次;

第(h-1)层有2个元素,它们最多比较(h-2)次;

第(h-2)层有22个元素,它们最多比较(h-3)次;...;

第1层有2(h-1)个元素,它们最多比较0次

所以,建堆的时间复杂度就是O(n)。

如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素

** 如何在O(n)的时间复杂度内查找一个无序数组中的第K个大元素?
*  第一次分区查找,我们需要对大小为 n 的数组执行分区操作,需要遍历 n 个元素。
* 
* 第二次分区查找,我们只需要对大小为 n/2 的数组执行分区操作,需要遍历 n/2 个元素。
* 
* 依次类推,分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.

* ……直到区间缩小为 1。
*  如果我们把每次分区遍历的元素个数加起来,就是:n+n/2+n/4+n/8+…+1

  * 这是一个等比数列求和,
* 
* 最后的和等于 2n-1。
所以,上述解决思路的时间复杂度就为 O(n)。

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

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

原始发表时间:2021-08-03

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java并发基础,不怕你看不懂!

    当我们使用计算机时,可以同时做许多事情,例如一边打游戏一边听音乐。这是因为操作系统支持并发任务,从而使得这些工作得以同时进行。

    Java3y
  • 高并发编程学习(1)——并发基础

    当我们使用计算机时,可以同时做许多事情,例如一边打游戏一边听音乐。这是因为操作系统支持并发任务,从而使得这些工作得以同时进行。

    我没有三颗心脏
  • 高并发编程学习(1)——并发基础

    当我们使用计算机时,可以同时做许多事情,例如一边打游戏一边听音乐。这是因为操作系统支持并发任务,从而使得这些工作得以同时进行。

    乔戈里
  • 代码里注释写太多,会挨打吗?

    前几天,有个同行朋友在我的微信上留言,问我项目代码里注释写太多会挨打吗?顺手还给我甩了一张截图,上面密密麻麻的全是手工注释。

    闰土大叔
  • 赫尔辛基大学AI基础教程:回归(4.3节)

    我们在本节中的主要学习目标是监督学习方法的另一个很好的例子,它也和最近邻分类一样简单:线性回归。以及它的近亲逻辑回归。

    AiTechYun
  • 走出NASA,向大地“下战书”,他要用卫星遥感数据改变中国农业

    图丨佳格天地创始人兼CEO张弓 【数据猿导读】“我国农业正处于传统农业向现代农业转变的关键时期,必须不失时机地促成飞跃。”在佳格天地创始人兼CEO张弓的眼中,在...

    数据猿
  • 人工智能做的肉,你想吃吗?

    编译自 BBC 原文作者 Jose Luis 原标题 Could AI help to create a meat-free world? 回想一下最近一次让...

    企鹅号小编
  • 科学技术的内涵和科技发明土壤——推进人类文明发展的引擎在哪里(4k字)

    数据相关的数学和科学、算法和程序、资源和简化、机构和活动、政策和新闻,请关注数据简化DataSimp社区!~

    秦陇纪
  • Python代码找bug(7)

    猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个;第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半...

    高一峰
  • Java学习笔记(4)——并发基础

    前言 当我们使用计算机时,可以同时做许多事情,例如一边打游戏一边听音乐。这是因为操作系统支持并发任务,从而使得这些工作得以同时进行。 那么提出一个问题:如果我...

    我没有三颗心脏
  • 用Python预测你的花呗可以用到什么时候!

    花呗给人一种“有钱”的感觉,我不禁思考:像我这种发工资前靠花呗活着,一发工资就还花呗的平静什么时候会打破,我要是还不起花呗了怎么办?

    小小詹同学
  • Facebook AI导致人被抓,谁来背锅?

    前段时间和Bittiger的冯总聊天。他有一个伟大的愿望,每天更新,争取写一万篇文章。这个让我深受启发。我意识到也许每天写点东西不是一个坏事。很多时候写作习惯是...

    用户1564362
  • 供地越多的地方,房价越涨吗?

    因此,我们经常会看到研究者们动不动就祭出一张全国地图,给每个城市进行评级,充满了指点江山的气魄。比如下图(来源:网络):

    华章科技
  • 编码规范 | Java函数优雅之道

    随着软件项目代码的日积月累,系统维护成本变得越来越高,是所有软件团队面临的共同问题。持续地优化代码,提高代码的质量,是提升系统生命力的有效手段之一。软件系统思维...

    一觉睡到小时候
  • 设计模式(九): 从醋溜土豆丝和清炒苦瓜中来学习"模板方法模式"(Template Method Pattern)

    今天是五.四青年节,祝大家节日快乐。看着今天这标题就有食欲,夏天到了,醋溜土豆丝和清炒苦瓜适合夏天吃,好吃不上火。这两道菜大部分人都应该吃过,特别是醋溜土豆丝,...

    lizelu
  • ML工作流程(第4部分) - 完整性检查和数据分割

    我们现在比特征提取领先一步,并且提取给定的原始数据的统计上重要的(协变量)表示。在特征提取之后,我们需要做的第一件事就是检查新的表示的值。通常,人们会认为这是浪...

    人工智能资讯小编
  • SolarWinds CEO首次回应“实习生泄露密码”言论:后悔

    当地时间5月19日,在RSAC 2021大会上,SolarWinds公司首席执行官Sudhakar Ramakrishna首次公布SloarWinds供应链攻击...

    FB客服
  • 年底跳槽,我来告诉你如何选择下一家公司?

    上周五,一位从成都离职,转战深圳发展的女粉丝,跟我微信私聊,问我找工作选择公司的问题,现在不知道要选择什么公司的offer。(插一句,都说土哥的这个号,是前端圈...

    闰土大叔
  • 神经网络的可解释性综述!

    Interpretability (of a DNN) is the ability to provide explanations in understand...

    统计学家

扫码关注云+社区

领取腾讯云代金券