时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度

时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度时间复杂度和空间复杂度如何计算?推导算法:大O推导法时间复杂度定义常数阶线性阶对数阶平方阶小结空间复杂度定义推导算法:大O推导法1、用常数1取代运行时间中的所有加法常数2、在修改后的运行次数函数中,只保留最高阶项3、如果最高阶项存在且不是1,那么我们就去除于这个项相乘的常数。时间复杂度定义在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

推导算法:大O推导法

1、用常数1取代运行时间中的所有加法常数
2、在修改后的运行次数函数中,只保留最高阶项 
3、如果最高阶项存在且不是1,那么我们就去除于这个项相乘的常数。

Jetbrains全家桶1年46,售后保障稳定

时间复杂度

定义

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n}=0(f(n))。它表示随问题规模n的增大,算法执行时间的埔长率和 f(n)的埔长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f( n)是问题规横n的某个函数。

常数阶

void main()
{ 
   
    func();
}
void func()
{ 
   
    int i=0;//执行1次
    i++;//执行1次
    i++;//执行1次
    i++;//执行1次
}
/* 共执行了4次,所以时间复杂度为O(4);根据大O推导法,略去常数,所以此函数的时间复杂度为O(1); */
//假如func变成如下结构
void func()
{ 
   
    int i=0;//执行1次
    i++;//执行1次
    i++;//执行1次
    i++;//执行1次
    i++;//执行1次
    i++;//执行1次 
    i++;//执行1次
    i++;//执行1次 
    i++;//执行1次 
    i++;//执行1次 
    i++;//执行1次 
    i++;//执行1次 
    i++;//执行1次
}
/* 共执行了13次,时间复杂度为O(13);根据大O推导法,略去常数,所以此函数的时间复杂度仍然为O(1); */

线性阶

void main()
{ 
   
   for(int i=0;i<n;i++)
    { 
   
        func();
    }
}
void func()//时间复杂度为O(1)的函数
{ 
   
   printf("大O推导法");//执行1次
}
/* 在main中,func共被执行了n次,所以main的时间复杂度为O(n); */
//加入main函数被修改成如下
void main()
{ 
   
   for(int i=0;i<n;i++)
    { 
   
        func();
        func();
    }
}
/* 在main中,func共被执行了2n次,main的时间复杂度为O(2n);根据大O推导法,略去常数系数,所以main的时间复杂度仍为为O(n); */

对数阶

void main()
{ 
   
   for(int i=1;i<n;i++)
    { 
   
        func();
        i=2i;
    }
}
void func()//时间复杂度为O(1)的函数
{ 
   
   printf("大O推导法");//执行1次
}
/* 在main中, 因为i每次被乘2,所以,执行的算法为 2的几次相乘 大于 n,即 2^x>n,--> x= log2n , 在推导对数时间复杂度时,一般都是以10作为对数的底数。 func共被执行了logn次,所以main的时间复杂度为O(logn); */

平方阶

void main()
{ 
   
   for(int i=1;i<n;i++)
    { 
   
       for(int j=1;j<n;j++)
        { 
   
            func();
        }
    }
}
void func()//时间复杂度为O(1)的函数
{ 
   
   printf("大O推导法");//执行1次
}
/* 在main中, func()共被执行了n^2,所以main的时间复杂度为O(n^2); */
//假如main被修改成 如下
void main()
{ 
   
   for(int i=1;i<n;i++)
    { 
   
       for(int j=i;j<n;j++)
        { 
   
            func();
        }
    }
}
/* 那么, func() 执行的次数为 n+n-1+n-2+……--> n(n+1)/2 = n2/2 + n/2 根据大O推导方法,保留最高阶项,n2/2 ,然后去掉这个项相乘的常数,1/2, 所以main的时间复杂度为O(n2) */

小结

在这里插入图片描述
时间复杂度所耗费的时间是:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) <O(2n) < O(n!) <O(nn)

参考 https://www.cnblogs.com/fanchangfa/p/3868696.html

空间复杂度

定义

百度百科:空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
算法类似于时间复杂度,只是计算的不是运行次数,而是在运行过程中临时变量被运用次数。

参考 https://www.cnblogs.com/irenebbkiss/p/4243715.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/219245.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • uc/os-II的内存改进与实现TLSF算法的详解,移植实现(二)[通俗易懂]

    uc/os-II的内存改进与实现TLSF算法的详解,移植实现(二)[通俗易懂]上一节讲到了TLSF的数据结构,下面继续哈。TLSF用两个层次的分类对不同尺寸的内存块进行分类。第一层次的类别目录为2n,n为4,5,……,31的整数,称为FLI(First-levelSegregatedFit)。每一个FLI类别又根据第二层的SLI细分为2SLI个子类别。第二层的每个类别,都对应一条属于该类别尺寸范围内的内存块链表。为了加快分配与合并内存块的速度,链表是不排序的。所有的

  • 定时任务框架Quartz-(一)Quartz入门与Demo搭建

    一、什么是Quartz什么是Quartz?Quartz是OpenSymphony开源组织在Jobscheduling领域又一个开源项目,完全由Java开发,可以用来执行定时任务,类似于java.util.Timer。但是相较于Timer,Quartz增加了很多功能:持久性作业-就是保持调度定时的状态;作业管理-对调度作业进行有效的管理;…

  • 如何利用净推荐值(NPS)测量用户忠诚度?

    如何利用净推荐值(NPS)测量用户忠诚度?用户满意度是每个企业都非常关心的问题,满意度水平高的企业往往也有着良好的营收效益。相反,用户满意度较差的企业,也可以通过用户满意度的相关调研,深入了解自己的不足之处,哪些方面有待改进。如何通过简单的数据指标,科学有效地测量出用户满意度呢?今天我们将为大家介绍一种调研用户满意度的常用方法——净推荐值(NPS)NPS是什么NPS即净推荐值(NetPromoterScore),是一种计量客户将会向其他人推荐企业或服务可能性的指数。是目前最流行的顾客忠诚度分析指标。NPS净推荐值的数据收集方

  • FAT32文件系统结构详解[通俗易懂]

    FAT32文件系统结构详解[通俗易懂]1.SD卡中FAT32文件系统快速入门1.1.理论知识1.1.1.MBR(MainBootRecord)主引导记录,占446字节,为计算机启动后从可启动介质上首先装入内存并且执行的代码,通常用来解释分区结构1.1.2.DBR(DOSBootRecord)DOS引导记录,为操作系统进入文件系统以后可以访问的第一个扇区,通常用来解释文件系统,DBR是由硬盘的MBR装…

    2022年10月22日
  • 在线打开pdm文件「建议收藏」

    在线打开pdm文件http://www.dmanywhere.cn/

  • centos7如何更改ip地址

    1.进入网络设置文件里面命令如下:这里最好是使用root用户,然后使用ls命令找到网络的配置文件。我这里的配置文件是ifcfg-ens33.然后使用vi命令进入文件进行编辑网络的ip地址等信息。然后按键盘i进入编辑模式,更改ip地址等信息。然后按esc键退出编辑模式,然后输入:wq!保存。2.使用servicenetworkrestart命令,重启网络服务。3.ping百…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号