算法的时间复杂度和空间复杂度

目录

1 如何衡量一个算法的好坏

2.时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3常见代码举例

 2.3.1 Func2        O(N)

 2.3.2 Func3        O(M+N)

 2.3.3 Func4        O(1)

 2.3.4 Func5    strchr   O(N)

 2.3.5 Func6   冒泡排序     O(N^2)

 2.3.6 Func7 二分查找(折半查找)        

 2.3.7 Func8阶乘递归        O(N)

 2.3.8 Func9斐波那契递归        O(N)

3 空间复杂度

3.1 Func1冒泡排序        O(1)

3.2 Func2斐波拉契数列        O(N)

3.3 Func3阶乘函数         O(N)

3.4 Func4 区分不同调用下的空间开辟

 3.4.1

 3.4.2​

3.5 Func5 Fib

4.常见复杂度


1 如何衡量一个算法的好坏

        算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般 是从时间和空间两个维度来衡量的,即 时间复杂度和空间复杂度
        时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

2.1 时间复杂度的概念

        时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一 个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例 算法中的基本操作的执行次数,为算法的时间复杂度
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度
Func1 执行的基本操作次数 :
F(N)=N^{2}+2*N+10 
        N = 10 F(N) = 130
        N = 100 F(N) = 10210
        N = 1000 F(N) = 1002010
        实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

2.2 O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后,Func1的时间复杂度为:
O(N^{2})
        N = 10 F(N) = 100
        N = 100 F(N) = 10000
        N = 1000 F(N) = 1000000
        通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

2.3常见代码举例

2.3.1 Func2        O(N)

 2.3.2 Func3        O(M+N)

 2.3.3 Func4        O(1)

 2.3.4 Func5    strchr   O(N)

 

有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
例如:在一个长度为N数组中搜索一个数据x
最好情况:1次找到
最坏情况:N次找到
平均情况:N/2次找到
在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

 

 2.3.5 Func6   冒泡排序     O(N^2)

最好:O(N);

(数组位置不清楚是否有序,所以至少要对相邻的两个数相互比较一次,至少比较n-1次)

最坏:O(N^2);

(第一轮比较n-1次,第二轮比较n-2次,……比较2次,最后剩最末的一对数,比较1次,等差数列 \frac{(n-1)(n-2)}{2}\rightarrow O(N^{2})

2.3.6 Func7 二分查找(折半查找)        O(log{_{2}}^{N}

最好:O(1);

最坏:log{_{2}}^{N}(不好写,在时间复杂度中,只有以2为底的才能简化为logN,其他底数不能简写,有些地方简写为lgN,但是我们不推荐这样写)

 

2.3.7 Func8阶乘递归        O(N)

 基本操作递归了N+1次,时间复杂度为O(N)

2.3.8 Func9斐波那契递归        O(N)

 现基本操作递归了2^N次,时间复杂度为O(2^N)

 2^30 10亿

2^40  10000亿

2^50  1亿亿

3 空间复杂度

        空间复杂度也是一个数学表达式,是对一个算法在运行过程中 临时占用(额外)存储空间大小的量度
        空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。
        空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

3.1 Func1冒泡排序        O(1)

 创建了红色框的三个变量,常数个变量,O(1);

3.2 Func2斐波拉契数列        O(N)

         额外开辟一个数组,O(N);malloc开n+1个空间,从0-n,n+1个

3.3 Func3阶乘函数         O(N)

 

 

3.4 Func4 区分不同调用下的空间开辟

 3.4.1

 3.4.2

 即递归空间开辟原理

3.5 Func5 Fib

前面我们讲过Fib时间复杂度是O(2^N)

                           空间复杂度呢?O(N)

4.常见复杂度

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3222.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

菜鸟刷题Day6

⭐作者:别动我的饭 ⭐专栏:菜鸟刷题 ⭐标语:悟已往之不谏,知来者之可追 一.链表内指定区间反转:链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com) 描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转…

如何用深度强化学习做单元测试代码生成

设计一个用强化学习来生成单元测试代码的系统需要考虑以下几个方面: Agent:强化学习算法中的智能体,它需要接收当前环境状态,根据策略选择相应的动作并执行。 State:描述当前环境状态的特征。在这个问题中&#xff0c…

电脑长按电源键强行关机,对SSD有伤害吗?SSD 掉盘之殇

说到“按住电源键强制关机”的操作,想必大家都不会陌生,毕竟在电脑蓝屏或者电脑死机的时候,我们总是束手无策。而且,身边的人在遇到同样的情况时,往往都是选择长按电源键强制关机,所以当我们遇到同样的情况…

【算法】回溯法详解

一、概述 回溯法在包含的所有可能解的解空间树中,从根节点出发,按照深度有限的策略进行搜索,对于解空间树的某个结点,如果该节点满足问题的约束条件,则进入该子树继续进行搜索,否则将以该节点为根节点进行…

【算法】一文详解贪心法

一、概述 贪心法将一个复杂问题分解为一系列较为简单的局部最优解,每一步都是对当前解的一个扩展,直到获得问题的完全解。贪心法的典型应用时求解最优化问题,而且即使是非最优解,最终得出的解也和最优解比较近似 1.1 贪心法设计…

【多线程】常见的锁策略

✨个人主页:bit me👇 ✨当前专栏:Java EE初阶👇 ✨每日一语:老当益壮,宁移白首之心;穷且益坚,不坠青云之志。 目 录🏳️一. 乐观锁 vs 悲观锁🏴二. 普通的互斥…

清晰概括:进程与线程间的区别的联系

相关阅读: 🔗通俗简介:操作系统之进程的管理与调度🔗如何使用 jconsole 查看Java进程中线程的详细信息? 目录 一、进程与线程 1、进程 2、线程 二、进程与线程之间的区别和联系 1、区别 2、联系 一、进程与线程 …

程序员接私活一定要知道的事情,我走的弯路你们都别走了

文章目录前言一、程序员私活的种类1.兼职职位众包2.自由职业者驻场3.项目整包二、这3种私活可以接1.有熟人2.七分熟的项目3.需求明确的项目三、这3种私活不要接1.主动找上门的中介单2.一味强调项目简单好做3.外行人给你拉的项目四、接单的渠道1.线下渠道2.线上渠道3.比较靠谱的…

计网之HTTP协议和Fiddler的使用

文章目录一. HTTP概述和fidder的使用1. 什么是HTTP2. 抓包工具fidder的使用2.1 注意事项2.2 fidder的使用二. HTTP协议格式1. HTTP请求格式1.1 基本格式1.2 认识URL1.3 方法2. 请求报头关键字段3. HTTP响应格式3.1 基本格式3.2 状态码一. HTTP概述和fidder的使用 1. 什么是HTT…

cpu中缓存简介

一级缓存是什么: 一级缓存都内置在CPU内部并与CPU同速运行,可以有效的提高CPU的运行效率。一级缓存越大,CPU的运行效率越高,但受到CPU内部结构的限制,一级缓存的容量都很小。 CPU缓存(Cache Memory&#xf…

【设计模式】23种设计模式之七大原则

【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…

冲击蓝桥杯-并查集,前缀和,字符串

目录 前言 一、并查集 1、并查集的合并(带路径压缩) 2、询问是否为同一个集合 3、例题 二、前缀和 1 、前缀和是什么 2、经典题目 三- 字符串处理 1、字符串的插入 2、字符串转化为int类型 3、字符反转 前言 并查集合前缀,字符串…

Python让ChatGPT全自动改写生成文章教程

ChatGPT是一个在自然语言处理领域非常先进的文本生成模型,它能够产生高质量、连贯的文章。它受到了广泛的关注,因为它可以自动生成大量的文本,从而减轻了人工写作的负担。怎么使用chatgpt批量改写文章?最简单的方式就是找到一家接…

「Vue面试题」vue要做权限管理该怎么做?如果控制到按钮级别的权限怎么做?

文章目录一、是什么二、如何做接口权限路由权限控制菜单权限方案一方案二按钮权限方案一方案二小结参考文章一、是什么 权限是对特定资源的访问许可,所谓权限控制,也就是确保用户只能访问到被分配的资源 而前端权限归根结底是请求的发起权,…

刷题之最长公共/上升子序列问题

目录 一、最长公共子序列问题(LCS) 1、题目 2、题目解读 ​编辑 3、代码 四、多写一题 五、应用 二、最长上升子序列问题(LIS) 1、题目 2、题目解读 3、代码 四、多写一道 Ⅰ、题目解读 Ⅱ、代码 一、最长公共子序列问题&…

刷题训练营之栈与队列

文章目录前言一、用队列实现栈1.题目介绍2.思路3.代码二、用栈实现队列1.题目介绍2.思路3.代码前言 本题是在栈与队列的基础上,为巩固两者而出的题,所以基本是在实现了栈与队列的基础上做的,如果没有栈与队列的基础,请看我之前的…

Nginx的漏洞浮现

本文参考https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/环境搭建均是采用docker拉取环境请移步到参考。一、Nginx的配置错误案列1. CRLF注入漏洞配置错误文件error1.confrootubuntu-virtual-machine:/vulhub/vulhub-master/nginx/insecure-configurati…

数据结构中的堆

一、树的重要知识点 节点的度:一个节点含有的子树的个数称为该节点的度(有几个孩子)叶节点或终端节点:度为0的节点称为叶节点;如上图:B、C、H、I...等节点为叶节点(0个孩子)非终端节点或分支节点…

css实现炫酷充电动画

先绘制一个电池&#xff0c;电池头部和电池的身体 这里其实就是两个div&#xff0c;使用z-index改变层级&#xff0c;电池的身体盖住头部&#xff0c;圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…

.NET Core 实现Excel的导入导出

.NET Core 使用NPOI实现Excel的导入导出前言NPOI简介一、安装相对应的程序包1.1、在 “管理NuGet程序包” 中的浏览搜索&#xff1a;“NPOI”二、新建Excel帮助类三、调用3.1、增加一个“keywords”模型类&#xff0c;用作导出3.2、添加一个控制器3.3、编写导入导出的控制器代码…