数据结构——算法的时间复杂度和空间复杂度

1、算法效率

1.1如何衡量一个算法的好坏?

比如我们最熟悉的斐波那契数列

long long Fib(int N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

上面的斐波那契数列使用递归实现,看起来非常的简洁,那么代码一定是越简洁越好么?

1.2算法的复杂度

一般的对于代码,我们如何检验代码的好坏呢?我们引入了复杂度,复杂度分为两种:时间复杂度和空间复杂度。

时间复杂度一般衡量的是一个算法运行的快慢。

空间复杂度一般衡量的是一个算法运行时所需要的额外空间。

2、时间复杂度

2.1时间复杂度的概念

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

定义这么长,归根结底我们来看个例子就一目了然了:

// 请计算一下Func1中++count语句总共执行了多少次?
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);
}

这里面我们可以看到,首先有一个双重for循环,两次循环的循环次数都是N,那么就是N*N,然后接着又有一个for循环循环次数是2N,最后还有一个M次数的for循环。

  • N = 10 F(N) = 130
  • N = 100 F(N) = 10210
  • N = 1000 F(N) = 1002010 

可以看到对于这个代码,上面的公式就是时间复杂度,我们将N分别带入看看,可以看出当N越大时,总数就越趋向于次方数较大的一方。实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

2.2大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后,Func1的时间复杂度为:

  • N = 10 F(N) = 100
  • N = 100 F(N) = 10000
  • N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。


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

2.3常见时间复杂度计算举例

实例1:

// 计算Func2的时间复杂度?
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);
}

实例2:

// 计算Func3的时间复杂度?
void Func3(int N, int M)
{
 int count = 0;
 for (int k = 0; k < M; ++ k)
 {
 ++count;
 }
 for (int k = 0; k < N ; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

实例3:

// 计算Func4的时间复杂度?
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

实例4:

// 计算strchr的时间复杂度?
const char * strchr ( const char * str, int character ){
    while(*str){
        if(*str == character){
            return str;
        }
        ++str;
    }
}

实例5:

// 计算BubbleSort的时间复杂度?
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

 实例6:

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]:begin和end是左闭右闭区间,因此有=号 while (begin <= end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;
 else
 return mid;
 }
 return -1;
}

 实例7:

// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
 if(0 == N)
 return 1;
 
 return Fac(N-1)*N;
}

 实例8:

// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

 实例答案及分析:
1. 实例1基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)
2. 实例2基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)
3. 实例3基本操作执行了10次,通过推导大O阶方法,时间复杂度为 O(1)
4. 实例4基本操作执行最好1次,最坏N次,时间复杂度一般看最坏,时间复杂度为 O(N)
5. 实例5基本操作执行最好N次,最坏执行了(N*(N+1)/2次,通过推导大O阶方法+时间复杂度一般看最
坏,时间复杂度为 O(N^2)
6. 实例6基本操作执行最好1次,最坏O(logN)次,时间复杂度为 O(logN) ps:logN在算法分析中表示是底
数为2,对数为N。有些地方会写成lgN。(建议通过折纸查找的方式讲解logN是怎么计算出来的)
7. 实例7通过计算分析发现基本操作递归了N次,时间复杂度为O(N)。
8. 实例8通过计算分析发现基本操作递归了2^N次,时间复杂度为O(2^N)。(建议画图递归栈帧的二叉树
讲解)

3、空间复杂度

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

实例1:

// 计算BubbleSort的空间复杂度?
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

实例2:

// 计算Fibonacci的空间复杂度?
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
 if(n==0)
 return NULL;
 
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
 return fibArray;
}

实例3:

// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

实例答案及分析:
1. 实例1使用了常数个额外空间,所以空间复杂度为 O(1)
2. 实例2动态开辟了N个空间,空间复杂度为 O(N)
3. 实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N) 

4. 常见复杂度对比 

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

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

相关文章

仰暮计划|“​爷爷说这些话的时候眼睛都红着,他那变形的脊柱和瘸拐的双腿都证明他曾为这个家付出了血汗拼尽了全力”

赴一场拾光之旅&#xff0c;集往年回忆碎片 爷爷生于1952年&#xff0c;今年已有七十一了&#xff0c;是河南焦作沁阳北金村的一位地道农民&#xff0c;劳苦一生&#xff0c;如今终于得以颐养天年。许是早年经历过于难忘&#xff0c;爷爷如今与我讲起仍是记忆犹新&#xff0c;…

kafka客户端生产者消费者kafka可视化工具(可生产和消费消息)

点击下载《kafka客户端生产者消费者kafka可视化工具&#xff08;可生产和消费消息&#xff09;》 1. 前言 因在工作中经常有用到kafka做消息的收发&#xff0c;每次调试过程中&#xff0c;经常需要查看接收的消息内容以及人为发送消息&#xff0c;从网上搜寻了一下&#xff0…

航道大数据应用专项研究报告(附下载)

总体目标 充分认识航道大数据对行业治理的重要性和必要性&#xff0c;航道大数据的开发和利用是建设智慧航道的基础。基于大数据的航道管理体系&#xff0c;实现了现有数据的梳理和汇聚&#xff0c;跨部门数据的交换和整合&#xff0c;建立了数据关联和深度学习的模型机制&…

【win】vscode无法使用ctrl+shift+p快捷键的解决方案

本文首发于 ❄️慕雪的寒舍 今天使用vscode的时候遇到的这个问题&#xff0c;明明快捷键设置的是ctrlshiftp&#xff0c;但是在电脑上怎么敲都敲不出来&#xff0c;因为用这个快捷键打开命令面板都习惯了&#xff0c;也不想换&#xff0c;就在找原因。 同时百度的时候还遇到了…

C++ 搜索二叉树的删除

首先查找元素是否在二叉搜索树中&#xff0c;如果不存在&#xff0c;则返回 要删除的结点可能分下面四种情况&#xff1a; a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中…

宠物空气净化器哪个牌子好?养猫家庭如何挑选宠物空气净化器?

养猫的朋友都知道&#xff0c;猫咪掉毛是一个令人头痛的问题。猫毛和皮屑会漂浮在空气中&#xff0c;不仅遍布全屋的各个角落&#xff0c;而且清理起来也非常麻烦&#xff0c;特别是那些难以清除的猫毛。更糟糕的是&#xff0c;这些猫毛还可能引发人们的过敏反应&#xff0c;如…

Excel——分类汇总

1.一级分类汇总 Q&#xff1a;请根据各销售地区统计销售额总数。 第一步&#xff1a;排序&#xff0c;我们需要根据销售地区汇总数据&#xff0c;我们就要对【销售地区】的内容进行排序。点击【销售地区】列中任意一个单元格&#xff0c;选择【数据】——【排序】&#xff0c…

parse库,一个优雅的python库

前言 在Python中&#xff0c;format方法和f-strings是两种常用的字符串插值方法。 name "Haige" age "18" print(f"{name} is {age} years old.")# Haige is 18 years old.而如果是要从字符串中提取期望的值呢&#xff1f;相信很多人的第一或…

代码随想录 Leetcode46. 全排列

题目&#xff1a; 代码&#xff08;首刷自解 2024年2月6日&#xff09;&#xff1a; class Solution { private:vector<vector<int>> res;vector<int> path; public:void backtracking(vector<int>& nums, int depth, vector<bool>& us…

CTF-PWN-堆-【chunk extend/overlapping-2】(hack.lu ctf 2015 bookstore)

文章目录 hack.lu ctf 2015 bookstore检查IDA源码main函数edit_notedelete_notesubmit .fini_array段劫持(回到main函数的方法) 思路格式化字符串是啥呢0x开头或者没有0x开头的十六进制的字符串或字节的转换为整数构造格式化字符串的其他方法 exp 佛系getshell 常规getshell ha…

【maven相关问题】Could not transfer artifact ...与Transfer failed for ...报错及解决办法

一、问题描述 拉取一个新项目后&#xff0c;maven解析下载文件时出现如下报错信息&#xff1a; 二、错误原因分析 提示信息是传输失败&#xff0c;无法传输的原因应该是出现错误的包文件夹已经缓存在本地存储库中&#xff0c;然后maven在经过发布的更新间隔或强制进行更新之前…

深入了解Spring Expression Language(SpEL)

深入了解Spring Expression Language&#xff08;SpEL&#xff09; Spring Expression Language&#xff08;SpEL&#xff09;是Spring框架中强大的表达式语言&#xff0c;它在运行时提供了一种灵活的方式来评估字符串表达式。SpEL的设计目标是在各种Spring配置和编程场景中提供…

Go语言每日一练链表篇(二)

传送门 牛客面试笔试必刷101题 ---------------- 链表内指定区间反转 题目以及解析 题目 解题代码及解析 package main import _"fmt" import . "nc_tools" /** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参…

PyTorch 2.2 中文官方教程(七)

使用 torchtext 库进行文本分类 原文&#xff1a;pytorch.org/tutorials/beginner/text_sentiment_ngrams_tutorial.html 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 注意 点击这里下载完整示例代码 在本教程中&#xff0c;我们将展示如何使用 torchtext 库构建文…

识别CMS指纹与WAF识别

目录 识别CMS指纹 1 什么是CMS指纹&#xff1f; 2 常见的CMS指纹 3 识别CMS指纹的方法有哪些&#xff1f; &#xff08;1&#xff09;分析HTTP响应头&#xff0c;识别CMS的特定标头。 &#xff08;2&#xff09;通过配置文件/特殊文件 &#xff08;3&#xff09;分析网站…

【Linux】命令行解释器脚本编写

&#x1f440;樊梓慕&#xff1a;个人主页 &#x1f3a5;个人专栏&#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》 &#x1f31d;每一个不曾起舞的日子&#xff0c;都是对生命的辜负 目录 前言 1.简单了解命令行解…

设计师常用的软件有哪些?推荐5款设计工具

设计软件的使用对设计师来说非常重要。设计工具的使用是否直接影响到最终结果的质量&#xff0c;然后有人会问&#xff1a;设计需要使用什么软件&#xff1f;这里有一些设计师和那些对设计感兴趣的朋友列出了五个有用的设计工具。 1、即时设计 即时设计操作简单&#xff0c;内…

Unity制作随风摇摆的植物

今天记录一下如何实现随风摇摆的植物&#xff0c;之前项目里面的植物摇摆实现是使用骨骼动画实现的&#xff0c;这种方式太消耗性能&#xff0c;植物这种东西没必要&#xff0c;直接使用顶点动画即可。 准备 植物不需要使用标准的PBR流程&#xff0c;基础的颜色贴图加上法向贴…

leetcode 算法 69.x的平方根(python版)

需求 给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&#xff0c;结果只保留 整数部分 &#xff0c;小数部分将被 舍去 。 注意&#xff1a;不允许使用任何内置指数函数和算符&#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1&#…

跳过mysql5.7密码并重置密码 shell脚本

脚本 目前只是验证了5.7 版本是可以的&#xff0c;8.多的还需要验证 以下是一个简单的Shell脚本&#xff0c;用于跳过MySQL密码设置并重置密码&#xff1a; #!/bin/bash yum install psmisc -y# 停止MySQL服务 sudo service mysqld stop# 跳过密码验证 sudo mysqld --skip-g…