时间复杂度和空间复杂度

简介: 时间复杂度和空间复杂度

😽个人主页: tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主

🌈梦的目标:努力学习,向Java进发,拼搏一切,让自己的未来不会有遗憾。

🎁欢迎各位→点

赞👍 + 收藏⭐ + 评论📝+关注✨

 本章讲解内容:时间和空间复杂度


5448c2884c44051acb97afda8b236e72.jpg


 使用编译器:IDEA

 今日毒汤:远方的路,因为未知,才值得去。

 

一.前言


如何衡量一个算法的好坏呢?方法:分析算法效率。


  算法效率分析分为两种:第一种是时间效率,时间效率被称为时间复杂度


                                          第二种是空间效率。空间效率被称作空间复杂度。


注:时间复杂度主要衡量的是一个算法的运行速度,空间复杂度主要衡量一个算法所需要的额外空间。


二.时间复杂度


2.1概述


      定义:算法的时间复杂度是一个数学函数,通过计算算法中的基本操作的执行次数,它定量描述了该算法的运行时间。


疑问:有人说,Java语言中有函数可以获取时间戳嘛,可以计算出代码运行的时间,这就错了,代码运行有很多外在因素影响。例如,电脑的硬盘大小、cpu、编译器的优良等。所以我们需要通过计算算法中的基本操作的执行次数来判断算法的优良。


2.2代码实例讲解


e4eebbb2a3c34398835966fdfdbd05a4.png


解析:


第一部分:外层循环N次,而每一次又会使内层循环N次,所以一共是 N² 次


第二部分:只循环 2N 次


第三部分:由于M=10,所以循环 10 次


计算方法:不需要计算精确的执行次数,且用常数1取代运行时间的所有加法常数。最后的结果:只保留最高阶项。


所以操作次数为: N²+2N+10 ;------>N²+N+1    去除N和1,保留最高阶项


时间复杂度为:       O(N²)


2.3递归的时间复杂度


计算方法:递归次数*每次递归执行次数


1. int fibonacci(int N) {
2. return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
3. }


该代码是菲波拉契数数,可以通过画二叉树来理解,可以看出它递归执行的次数是2 的n次方,所以次,时间复杂度为O(2^n )。


2.4 情况分类


时间复杂度分为3种情况,最坏情况:最后一次找到


                                        平均情况:   最坏次数/2


                                        最好情况:   第一次找到


实际中,我们表达的时间复杂度为最坏情况。


三.空间复杂度


     空间复杂度:算法运行过程中临时占用空间大小的度量。计算的是变量的个数。


计算方法:

  1. 常数个空间,空间复杂度为 O(1)
  2. 动态开辟了N个空间,空间复杂度为 O(N)
  3. 递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

注:情况都存在时,取最大值。


实例1:

public class Text1 {
    public static void main(String[] args) {
         int a=10;
         float b=20.2f;
         double cc=22.5;
    }
}


代码中便全是常数,因此空间复杂度为O(1)

实例2:

 public  void text(int n)
    {
       int[] a=new int[n];
      }


方法text 开辟了N个空间,所以看见复杂度为O(n)

实例3:

1. int text(int N) {
2. return N < 2 ? N : text(N-1)*N;
3. }


递归调用了N次,因此空间复杂度为O(n)

注:

有多因素会影响程序真正内存使用大小

例如编译器的内存对齐,编程语言容器的底层实现等等


总结


       时间复杂度的重要性比空间复杂度要高,理由:人们越来越追求效率了,而空间越来越不值钱了,1T硬盘也不贵。因此我们可以牺牲空间成全时间。

目录
相关文章
|
机器学习/深度学习 人工智能 物联网
Facechain使用教程:3张照片就能生成个人写真,还完全免费
下面4张图片,小伙伴们有没有看出来哪些是原图,哪些是AI生成的呢?
1062 0
|
人工智能 编解码
AI 绘画Stable Diffusion 研究(二)sd模型ControlNet1.1 介绍与安装(2)
AI 绘画Stable Diffusion 研究(二)sd模型ControlNet1.1 介绍与安装
641 0
|
存储 算法 数据挖掘
【2023年中国高校大数据挑战赛 】赛题 B DNA 存储中的序列聚类与比对 Python实现
本文介绍了2023年中国高校大数据挑战赛赛题B的Python实现方法,该赛题涉及DNA存储技术中的序列聚类与比对问题,包括错误率分析、序列聚类、拷贝数分布图的绘制以及比对模型的开发。
289 2
【2023年中国高校大数据挑战赛 】赛题 B DNA 存储中的序列聚类与比对 Python实现
怎么能快速注册商标和域名联系
怎么能快速注册商标和域名联系
202 1
|
数据库 数据安全/隐私保护 数据库管理
基于SpringBoot+Vue健身房管理系统(源码+部署说明+演示视频+源码介绍)(2)
基于SpringBoot+Vue健身房管理系统(源码+部署说明+演示视频+源码介绍)
270 1
|
搜索推荐 项目管理 开发工具
odoo是啥
【6月更文挑战第23天】odoo是啥
684 3
|
存储 Java
Java中带返回值方法的定义与调用技术
Java中带返回值方法的定义与调用技术
233 1
|
机器学习/深度学习 存储 人工智能
【OpenVI-视觉评价系列之MOS评价实战篇】手机存储不够用,清理照片太痛苦?MOS评价帮你挑选“垃圾”照片
MOS(Mean Opinion Score)是一种常用的主观质量评价方法,常用于视频、图像等多媒体领域中的质量评价。MOS视觉评价通常是通过让受试者观看视频/图像,对视频的清晰度、锐度、颜色饱和度、运动模糊、噪声等方面进行评价。然而,MOS视觉评价也存在一些局限,例如需要大量的受试者,评估时间较长等。因此,近年来,研究者们也开始探索使用客观评价方法来替代或补充MOS视觉评价。
858 2
【OpenVI-视觉评价系列之MOS评价实战篇】手机存储不够用,清理照片太痛苦?MOS评价帮你挑选“垃圾”照片
|
机器学习/深度学习 搜索推荐 算法
【前沿解读】17篇2023淘天业务技术A类顶会论文(下)
【前沿解读】17篇2023淘天业务技术A类顶会论文(下)
455 3
|
自然语言处理 监控 项目管理
项目十大管理(五)质量管理
* 从项目作为一次性活动来看,项目质量体现在由WBS反映出的项目范围内所有的阶段、子项目、项目工作单元的质量所构成,即项目的工作质量 * 从项目作为一项最终产品来看,项目质量体现么在其性能或者使用价值上,即项目的产品质量。项目合同通常是进行项目质量管理的主要依据。
557 1