首页 > 编程语言 >【算法学习】算法时间复杂度

【算法学习】算法时间复杂度

时间:2024-08-12 15:54:00浏览次数:8  
标签:函数 递归 复杂度 学习 算法 循环 时间

时间复杂度的计算

时间复杂度简单计算(一层、两层、多层循环)

相当于轨迹追踪法:设执行次数为k,按照循环条件

image-20230530085749739

image-20230530085814900

image-20230530085959529

img

阿布算法课

学习链接

01 区别算法(Algorithm)和程序(Program)


image-20230530094414979

算法程序
设计阶段 实施阶段
相关领域知识 程序员
任何语言、伪代码 编程语言
独立于硬件/操作系统 与硬件/操作系统有关
算法分析 程序测试

02 事前分析和事后测试

image-20230530094503082

事前分析事后测试
算法 程序
独立于语言 有赖于语言
独立于硬件/操作系统 与硬件/操作系统有关
时间/空间 复杂度函数 运行时间/占用字节

03 算法的性质

image-20230531110336615

  • 一个或多个输入

  • 至少有一个输出

  • 可定义性

  • 有限性

  • 高效性

04 算法的表示和分析

怎么表示一个算法:需要看得懂,没有固定形式(伪代码)

如何分析一个算法?

  • Time:时间消耗

  • Space:内存消耗

  • N/W:数据传输和网络消耗

  • Power:能耗

  • CPU Registers:占用CPU多少寄存器(底层驱动、操作系统)

时间复杂度分析 image-20230530100626462

image-20230530101100153 时间复杂度函数 f(n) = 3

  • 算法时间复杂度分析,不需要考虑每个陈述语句形式。

  • 算法时间复杂度看的是常数操作总次数

05 频数分析法求时间间复杂度

一层循环 image-20230530150458437

两层循环 image-20230530151453960

多层循环 image-20230530151221152

06 轨迹追踪法求时间复杂度

设执行次数为k,按照循环条件,得出执行次数k与问题规模n的关系,从而得时间复杂度 image-20230531093157591

07 时间复杂度分析示例

image-20230531094351683

logn为小数,执行次数要向上取整

image-20230729174259316

image-20230531095047155

image-20230531100024461

image-20230729174549492

image-20230729174745754

image-20230729174844300

常见for循环时间复杂度总结:

image-20230531110108500

08 while循环、if条件的时间复杂度分析

由于while循环可以和for循环相互转换,while循环实际上和for循环分析方法一样

if 语句分析时间复杂度可能有最坏、最好情况

image-20230729180257132 image-20230531112251026

image-20230729180526275

09 时间复杂度的分类

image-20230729181417244

10 函数复杂度的比较和分析

image-20230529220533633

增长速度:常<对<幂<指数

11函数的渐近符号

image-20230529215813204

image-20230529215850457

image-20230730144546461

上界有很多,尽量使用最接近的那个上界表示f(n)

image-20230529215933551

image-20230730144850423

当下界有很多时,尽量使用最接近的那个下界表示f(n)

image-20230529220003277

image-20230730145050590

平均界只有一种表示方式表示f(n)


最好、最坏、平均情况的时间复杂度

  • 算法的时间复杂度,会随着排序集合的有序性而改变。我们需要分析不同算法在不同数据下的表现

    • 最好时间复杂度:在完全有序的情况下的时间复杂度

    • 最坏时间复杂度:在最坏情况下的时间复杂度

    • 平均复杂度:平均情况下的时间复杂度

注意:并不是最坏时间复杂度就用O(n),最好情况就是\Omega(n),平均情况就是\theta(n),O(),\Omega(),\theta()只是表示函数渐近的符号,都可以使用任何情况的时间复杂度衡量上。

最好、最坏、平均情况时间复杂度分析

线性搜索

image-20230730194151540

image-20230730194328240

image-20230730194454552

二叉搜索树(二叉排序树)(二分搜索)

image-20230730203426113

12深入学习函数渐近符号

image-20230730150255092

image-20230730150443483

image-20230730150628896

阶乘形式的f(n)没有精确的平均界表示,只能通过上、下界表示

logn! = O(nlogn) = Ω(1)

13 渐近符号的性质

image-20230730151125219

image-20230730151544708

14 函数的比较

image-20230730151736923

image-20230730151857022

image-20230730152021321


15 递归算法的时间复杂度

  • 整个递归算法的时间复杂度函数用 T(n)表示

  • 如何求得递归算法得时间复杂度函数T(n):

    • 递归追踪树,求得T(n)表达式

    • 由T(n)的递推关系,推导出T(n)

    • 根据master公式得出T(n)的渐近表示

例1

image-20230730154209599

例2

image-20230730154922868

追踪递归树求T(n)

image-20230730155239105

递归推导求T(n)

image-20230730155416624

常见T(n)递归关系对应的时间复杂度

image-20230531155318804 image-20230531155742957

16 master公式

减法的master公式

Masters Theorem Decreasing Function

image-20230531160610777

除法的master公式

Masters Theorem in Algorithms for Dividing Function image-20230531162017499


左神求递归复杂度:(以上的p=0的情况)

image-20230524092133794 N^d*logN 即 N^dlogN

其中:

  • T(N) 是问题规模为 N 时递归算法的时间复杂度

  • a(a>0)是子问题数量,子问题的规模相同,每一个子问题约耗时 T(N/b)

  • b 是问题规模缩减的程度,通常 b > 1

  • O(n^d) 是非递归部分的时间复杂度,通常较低阶


标签:函数,递归,复杂度,学习,算法,循环,时间
From: https://www.cnblogs.com/SaturnRing/p/18355137

相关文章

  • 【办公软件学习】解决在打开word时,出现 “word 在试图打开文件时遇到错误” 的问题
    1.问题描述:最近在网上查找期刊论文的模板时,发现从期刊官网下载下来的论文格式模板,在本地用word打开时,出现错误,情况如下2.解决办法关闭提示窗口,打开左上角的【文件】按钮点击【选项】按钮点击【信任中心】>>>>【信任中心设置】选择【受保护视图】选项卡,将右侧窗口中......
  • 【办公软件学习】如何交叉引用多个参考文献[x-x]
    参考文献第一步:点击交叉引用将[24]、[27]这两个文献插入。第二步:右键刚插入的文献序号,然后点击切换域代码第三步:在代码块中添加代码\#"[0"和\#"0]"第四步:右键刚编辑的代码块,并更新域。第五步:在[4547]之间添加-,之后按"ctrl"+"shift"+"+"改成上标形式     ......
  • 【办公软件学习】如何将Word格式转换为Markdown格式
    一键!将Word转换为Markdown参考链接1:https://zhuanlan.zhihu.com/p/30891168参考链接2:https://blog.csdn.net/qq15035899256/article/details/125547483参考链接3:https://word2md.com/方法一:Writage+Pandoc—双剑合璧!下载并安装Writage,下载地址:http://www.writage.c......
  • Java基础-学习笔记08
    01类变量、类方法、main方法、代码块类变量(静态变量)类变量也叫静态变量/静态属性,是该类的所有对象共享的变量,任何一个该类对象去访问它时,取到的都是相同的值,同样任何一个该类的对象去修改它时,修改的也是同一个变量。关于静态变量在内存中的存放地址,有两种说法,①认为静态变量......
  • HCL学习——交换机端口安全技术
    本篇记录学习HCL的笔记。【2023年】H3CNE认证网络工程师完整培训视频教程_上https://www.bilibili.com/video/BV1Dg411i7yM?p=22&spm_id_from=pageDriver&vd_source=ecbebcd4db8fad7f74c518d13e78b165 802.1x技术 如果随便拿台pc插到交换机上岂不是就能接入本公司网络呢,80......
  • 操作系统实验学习进度
    最近开始学习操作系统和机组的相关知识,写一个学习进度的笔记作为鞭策,其中的dayn不一定全是一天内完成的,同时,大部分文字来源于学习资料rCore-Tutorial-Book第三版。Day0-入门操作系统初步介绍1.定义一个操作系统(OS)是一个软件,它帮助用户和应用程序使用和管理计算机的......
  • 零基础学习人工智能—Python—Pytorch学习(四)
    前言接续上一篇的optimizer的学习。optimizer代码和上一篇文章的一样,如下:importtorchimportnumpyasnpimporttorch.nnasnnX=torch.tensor([1,2,3,4],dtype=torch.float32)Y=torch.tensor([2,4,6,8],dtype=torch.float32)w2=torch.tensor(0.0,requ......
  • HCL学习——生成树STP
     本篇记录学习HCL的笔记。【2023年】H3CNE认证网络工程师完整培训视频教程_上 https://www.bilibili.com/video/BV1Dg411i7yM/?p=15&vd_source=ecbebcd4db8fad7f74c518d13e78b165连两根线目的为了备用线路,增加可靠性。但会产生广播风暴和mac地址表振荡。 生成树只解决二层......
  • node.js 学习
    今天为大家推荐一款VSCode的插件FittenCode,FittenCode是由非十大模型驱动的AI编程助手,它可以自动生成代码,提升开发效率,帮您调试Bug,节省您的时间,另外还可以对话聊天,解决您编程碰到的问题。https://www.runoob.com/nodejs/fitten-code-nodejs.html#post-25998-10更改node......
  • [算法] 2-SAT简记
    真的是简记2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题(就是有没有解以及输出一种方案);其实可以类比二分图最大匹配(但其实两者的差别还是很大的);算法流程对于每一个变量,我们都有两种情况,$true$和$false$;而题目中给我们的,是形如{$A=true/false$或......