时间复杂度与空间复杂度

我们知道算法的效率分为时间效率和空间效率,接下来我们就对这两者进行讨论。

一.时间复杂度.

又被称为时间效率,主要反映一个算法的运行速度。

定义:计算机算法中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间,一个算法所发挥的时间与其中语句的执行次数成正比,算法中的基本操作的执行次数为算法的时间复杂度

下面我们就通过具体实例来慢慢学会它!

例一:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Func1(int N)
{int count = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){++count;}}for (int k = 0; k < 2 * N; k++){++count;}int M = 10;while (M){++count;}printf("%d\n", count);}
int main()
{int N = 0;scanf("%d", &N);Func1(N);return 0;
}

看这个代码,问题来了,请问它一共循环多少次?

结果为:N*N+N*2+10

接下来我们就可以看看时间复杂度了。

首先,时间复杂度是一个估算,是看表达式中对其影响最大的一项(当N趋近无穷大

时),所以对于上面这个表达式,N*N对时间复杂度影响最大,就取它。

接下来我们用大O渐进法来表示:

对于上表达式:O(N^2)

understand?

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数

2、在修改后的运行次数函数中,只保留最高阶项

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后,Func1的时间复杂度为:O(N^2)

接下来我们一题来分析上述情况:

例二:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; k++){++count;}int M = 10;while (M){++count;}printf("%d\n", count);}
int main()
{int N = 0;scanf("%d", &N);Func2(N);return 0;
}

求其时间复杂度:

首先循环次数:2*N+10

时间复杂度为:O(N)-----对于上面规律三的运用

例三:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Func3(int N,int M)
{int count = 0;for (int i = 0; i < N; i++){count++;}for (int j = 0; j < M; j++){count++;}printf("%d\n", count);
}
int main()
{int N = 0;int M = 0;scanf("%d %d", &N,&M);Func3(N,M);return 0;
}

求其时间复杂度?

循环次数:M+N

时间复杂度:我们发现这题要分类讨论

1.当M与N大小差不对时,O(M)  ,O(N)都行

2.当M远大于N时,O(M)

3.当N远大于M时,O(N)

例四:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Func3(int N)
{int count = 0;for (int i = 0; i < 100; i++){count++;}printf("%d\n", count);
}
int main()
{int N = 0;scanf("%d %d", &N);Func3(N);return 0;
}

求其时间复杂度:

循环次数:100

时间复杂度:O(1)

常数1取代运行时间中的所有加法常数

满足公式1

例五:

const char* Func5(char* a, char b)
{while (*a != '\0'){if (*a == b){return a;a++;}}return NULL;
}

求时间复杂度?

有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数(上界)

评均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界)
例如:在一个长度为N数组中搜索一个数据x

最好情况:1次找到
最坏情况: N次找到
平均情况: N/2次找到
在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

对于这题,同理;由于不知道会循环多少次,所以我们按最坏情况来写,即O(N)

例六:

void Bubblesort(int* a, int n)
{for (int i = 0; i < n-1; i++){for (int j = 0; j < n-1 - i; j++){if (*(a + j) > *(a + j + 1)){int tmp = *(a + j);*(a + j) = *(a + j + 1);*(a + j + 1) = tmp;}}}
}

求其时间复杂度?

循环次数:第一趟:N-1

                  第二趟:N-2

                  ……

                  第N-1趟:1

所以总共:     ( N*(N+N-1))/2

时间复杂度:O(N^2)

例七:

int Binarysearch(int* arr, int n, int x)
{int left = 0;int right = n;while (left < right){int mid = (left + right) / 2;if (x > arr[mid]){left = mid + 1;}if (x < arr[mid]){right = mid - 1;}if (x== arr[mid]){return mid;}}return -1;
}

求时间复杂度?

循环次数:

对于该题又要分情况讨论了

1,可能一次就可以-----最好情况O(1)

2.最坏情况:

要X次:2^X=N    =>   log2N(2是底数)

时间复杂度:0(logN)

注意:算法的复杂度计算,喜欢省略简写成logN,因为很多地方不好写底数,有些书本,或者网上资料会写成O (lgN),严格来说这个不对的

例题八:

long long int Factorial(int n)
{return n < 2 ? n : Factorial(n - 1) * n;
}

求时间复杂度?

循环次数:递归了N次

时间复杂度:0(N)

常见时间复杂度分析:

通过对比我们发现:

不同的时间复杂度是存在非常大的差距的,我们能实现越小越好。

二.空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法

我们还是通过例题来比较:

例一:

void Bubblesort(int* arr, int n)
{for (int i = 0; i < n-1; i++){for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}
}

首先:在这里,我们要明白时间是累计的,空间是不累计,所以,对于这题,我们发现变量只有3个(参数不算),大O渐进法表示为:O(1)

注意:该循环走了N次,重复利用的是一个空间

例二:

long long int Factorial(int n)
{return n < 2 ? n : Factorial(n - 1) * n;
}

算空间复杂度?

递归只在整体返回时才消除栈帧,递归调用了N层,每次调用建立一个栈帧,每个栈帧使用了常数个空间 ,所以空间复杂度为:O(1)

最后,诸君共勉!!!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

在无回显的情况下如何判断是否存在命令注入漏洞

在无回显的情况下如何判断是否存在命令注入漏洞 这种情况下可以使用OOB带外来实现&#xff0c;言而简之&#xff0c;就是利用命令执行漏洞去解析我们的dns如果dns日志有记录那就说明存在命令注入漏洞 首先先简单搭建一个无回显的命令注入 <?phpexec($_REQUEST[777]); ?&…

使用sonar对webgoat进行静态扫描

安装sonar并配置 docker安装sonarqube&#xff0c;sonarQube静态代码扫描 - Joson6350 - 博客园 (cnblogs.com) 对webgoat进行sonar扫描 扫描结果 bugs Change this condition so that it does not always evaluate to "false" 意思是这里的else if语句不会执行…

前端字典的使用

这是data里的数据&#xff1a; 这是数据展示&#xff1a;

Vue2系列 -- 组件自动化全局注册(require.context)

参考官网&#xff1a;https://v2.cn.vuejs.org/v2/guide/components-registration.html 1 作用 省略 import 引入组件 省略 在main.js 中注册 实现自动化引入组件 2 自定义文件夹 在 src 下新建一个 components/base 文件夹&#xff0c;用于存放要自动注册的组件 3 在 base…

抖音seo短视频矩阵源码开发部署与维护--开源

一、引言 随着抖音等短视频平台的崛起&#xff0c;越来越多的企业和个人开始关注如何在这些平台上提升曝光量和用户流量。抖音SEO&#xff08;搜索引擎优化&#xff09;是一种有效的方法&#xff0c;通过优化短视频内容和关键词&#xff0c;让更多的人找到并点击你的视频。本文…

openGauss学习笔记-129 openGauss 数据库管理-参数设置-查看参数值

文章目录 openGauss学习笔记-129 openGauss 数据库管理-参数设置-查看参数值129.1 操作步骤129.2 示例 openGauss学习笔记-129 openGauss 数据库管理-参数设置-查看参数值 openGauss安装后&#xff0c;有一套默认的运行参数&#xff0c;为了使openGauss与业务的配合度更高&…

.NET 8.0 AOT 教程 和使用 和 .NET ORM 操作

NET AOT编译是一种.NET运行时的编译方式&#xff0c;它与传统的JIT编译方式不同。在传统的JIT编译中&#xff0c;.NET应用程序的代码在运行时才会被编译成本地机器码&#xff0c;而在AOT编译中&#xff0c;代码在运行之前就被提前编译成本地机器码。这样可以在代码运行的时候不…

JetLinks设备接入的认识与理解【woodwhales.cn】

为了更好的阅读体验&#xff0c;建议移步至笔者的博客阅读&#xff1a;JetLinks设备接入的认识与理解 1、认识 JetLinks 1.1、官网文档 官网&#xff1a;https://www.jetlinks.cn/ JetLinks 有两个产品&#xff1a;JetLinks-lot和JetLinks-view 官方文档&#xff1a; JetLi…

系列六、ThreadLocal内存泄露案例

一、ThreadLocal内存泄露案例 /*** Author : 一叶浮萍归大海* Date: 2023/11/22 10:56* Description: 写一段代码导致内存泄露* VM Options&#xff1a;-Xms20m -Xmx20m -Xmn10m -XX:PrintGCDetails* 说明&#xff1a;内存泄露最终会导致内存溢出*/ public class ThreadLocalO…

【Docker】从零开始:3.Docker运行原理

【Docker】从零开始&#xff1a;3.Docker运行原理 Docker 工作原理Docker与系统的关系Docker平台架构图解 Docker 工作原理 Docker与系统的关系 Docker 是一个 Client-Server 结构的系统&#xff0c;Docker 守尹进程运行在王机上&#xff0c; 然后通过 Socket 连接从各尸端坊…

赛氪荣幸受邀参与中国联合国采购促进会第五次会员代表大会

11 月21 日 &#xff08;星期二&#xff09; 下午14:00&#xff0c;在北京市朝阳区定福庄东街1号中国传媒大学&#xff0c;赛氪荣幸参与中国联合国采购促进会第五次会员代表大会。 2022年以来&#xff0c;联合国采购杯全国大学生英语大赛已经走上了国际舞台&#xff0c;共有来自…

CleanMyMac X4.16免费版mac电脑一键清理电脑垃圾工具

但是&#xff0c;我最近发现随着使用时间的增加&#xff0c;一些奇奇怪怪的文件开始占据有限的磁盘空间&#xff0c;存储空间变得越来越小&#xff0c;系统占用空间越来越大&#xff0c;越来越多的无效文件开始影响我电脑的运行速度。 Mac的文件管理方式和Windows不太一样&…

【Django使用】4大模块50页md文档,第4篇:Django请求与响应和cookie与session

当你考虑开发现代化、高效且可扩展的网站和Web应用时&#xff0c;Django是一个强大的选择。Django是一个流行的开源Python Web框架&#xff0c;它提供了一个坚实的基础&#xff0c;帮助开发者快速构建功能丰富且高度定制的Web应用 Django全套笔记地址&#xff1a; 请移步这里 …

代码随想录算法训练营|五十九~六十天

下一个更大元素|| 503. 下一个更大元素 II - 力扣&#xff08;LeetCode&#xff09; 和每日温度一样的套路&#xff0c;就是这里可以循环数组&#xff0c;两个数组拼接&#xff0c;然后循环两遍就行。 public class Solution {public int[] NextGreaterElements(int[] nums)…

redis之主从复制和哨兵模式

&#xff08;一&#xff09;redis的性能管理 1、redis的数据缓存在内存中 2、查看redis的性能&#xff1a;info memory&#xff08;重点&#xff09; used_memory:904192&#xff08;单位字节&#xff09; redis中数据占用的内存 used_memory_rss:10522624 redis向操作系统…

asp.net mvc点餐系统餐厅管理系统

1. 主要功能 ① 管理员、收银员、厨师的登录 ② 管理员查看、添加、删除菜品类型 ③ 管理员查看、添加、删除菜品&#xff0c;对菜品信息进行简介和封面的修改 ④ 收银员浏览、搜索菜品&#xff0c;加入购物车后进行结算&#xff0c;生成订单 ⑤ 厨师查看待完成菜品信息…

文心一言 VS 讯飞星火 VS chatgpt (140)-- 算法导论11.4 5题

五、用go语言&#xff0c;考虑一个装载因子为a的开放寻址散列表。找出一个非零的a值&#xff0c;使得一次不成功查找的探查期望数是一次成功查找的探查期望数的 2 倍。这两个探查期望数可以使用定理11.6 和定理 11.8 中给定的上界。 文心一言&#xff0c;代码正常运行&#xf…

铸就匠心,打造西部最具权威的行业商会组织

中国商报陕西报道&#xff08;记者 朱清平&#xff09;西安市五金机电商会(以下简称商会)第二届一次会员代表大会暨新任理事、监事就职典礼于11月17日在西安经开洲际酒店召开。 商会于2018年10月成立,在5年的发展中,依托“一带一路”发展的“快车道”,通过新丝路国际工业品数字…

分享给自媒体人:做自媒体最好的心态

做自媒体路上的两大修行&#xff1a; 一是状态不好的时候&#xff0c;明知道停更会掉流量&#xff0c;依然可以毫不焦虑地躺平; 二是发的东西没人看&#xff0c;坚持更新也没流量&#xff0c;却依然可以坚定地做自己。 做号这件事&#xff0c;就是一分耕耘一分收获的。 可能有人…

感恩节的习俗 Custom of Family Dinner

感恩节是美国最普遍庆祝的传统节日之一。在每年11月的第四个星期四&#xff0c;感恩节如期而至。Thanksgiving is one of the most universally celebrated traditional American holidays. Every year, Thanksgiving arrives on the fourth Thursday of November without fail…