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

时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度时间复杂度和空间复杂度如何计算?推导算法:大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)
blank

相关推荐

  • 在虚拟机上安装XP系统「建议收藏」

    在虚拟机上安装XP系统「建议收藏」WindowsXP番茄家园的安装点击”文件”–>”新建”–>”虚拟机”–>弹出”新建虚拟机向导”的欢迎界面.–>”下一步”配置你的新虚拟机,选择”典型”–>”下一步”选择客户机操作系统–>”MicrosoftWindows”-,版本:WindowsXPProfessional–>”下一…

  • SphinX人像识别 — 联想笔记本人脸识别系统 (适合所有带摄像头的电脑)

    SphinX人像识别 — 联想笔记本人脸识别系统 (适合所有带摄像头的电脑)

  • PXE网络

    PXE网络PXE原理和概念PXE严格来说并不是一种安装方式,而是一种引导的方式。进行PXE安装的必要条件是要安装的计算机中包含一个PXE支持的网卡(NIC),即网卡中必须要有PXEClient。PXE(Pre-bootExecutionEnvironment)协议使计算机可以通过网络启动。协议分为client和server端,PXEclient在网卡的ROM中,当计算机引导时,BIOS把PXEclient调入内存执行,由PXEclient将放置在远端的文件通过.

  • 什么是Unix时间戳?(转载)[通俗易懂]

    什么是Unix时间戳?(转载)[通俗易懂]Unix时间戳(Unixtimestamp),或称Unix时间(Unixtime)、POSIX时间(POSIXtime),是一种时间表示方式,定义为从格林威治时间1970年01月01日00时00

  • java环境变量 的配置与详解(全网最详细教程)

    java环境变量 的配置与详解(全网最详细教程)笔者这学期开始学习java课程,学习java开发首先需要配置java运行环境变量。虽然上课老师也讲了如何配置java环境变量,可是笔者的同学还是有好多都不会配置,所以笔者最近配置了特别多次java环境变量。如下笔者详细解释从JDK安装到环境变量的装配。目录 JDK的下载与安装 配置java环境变量JAVA_HOME变量Path变量ClassPath变量classpath…

  • unbuntu安装google浏览器和谷歌浏览器驱动

    unbuntu安装google浏览器和谷歌浏览器驱动1、安装google浏览器sudowgethttp://www.linuxidc.com/files/repo/google-chrome.list-P/etc/apt/sources.list.d/wget-q-O-https://dl.google.com/linux/linux_signing_key.pub|sudoapt-keyadd-sudoapt-…

发表回复

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

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