【初阶数据结构】1.算法复杂度
文章目录
- 1.数据结构前言
- 1.1 数据结构
- 1.2 算法
- 1.3 如何学好数据结构和算法
- 2.算法效率
- 2.1 复杂度的概念
- 2.2 复杂度的重要性
- 3.时间复杂度
- 3.1 大O的渐进表示法
- 3.2 时间复杂度计算示例
- 3.2.1 示例1
- 3.2.2 示例2
- 3.2.3 示例3
- 3.2.4 示例4
- 3.2.5 示例5
- 3.2.6 示例6
- 3.2.7 示例7
- 4.空间复杂度
- 4.1 空间复杂度计算示例
- 4.1.1 示例1
- 4.1.2 示例2
- 5.常见复杂度对比
- 6.复杂度算法题
- 6.1 旋转数组
1.数据结构前言
1.1 数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用,所以我们要学各式各样的数据结构。
如:线性表、树、图、哈希等
1.2 算法
算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。
1.3 如何学好数据结构和算法
秘诀1:
死磕代码!!!
秘诀2:
画图画图画图+思考
2.算法效率
例题:
力扣189.轮转数组:
给定一个整数数组 nums
,将数组中的元素向右轮转 k
个位置,其中 k
是非负数。
void rotate(int* nums, int numsSize, int k) {while(k--){int end = nums[numsSize-1];for(int i = numsSize - 1;i > 0 ;i--){nums[i] = nums[i-1];}nums[0] = end;}
}
这个算法是没有问题的,但是在力扣运行会报错,显示超过时间限制。
这就涉及到了复杂度这个概念。
2.1 复杂度的概念
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般 是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算 机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.2 复杂度的重要性
复杂度在校招中的考察已经很常见,要重点掌握。
3.时间复杂度
定义:在计算机科学中,算法的时间复杂度是一个函数式T(N)
,它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率,那么为什么不去计算程序的运行时间呢?
因为程序运行时间和编译环境和运行机器的配置都有关系,比如同一个算法程序,用一个老编译器进行编译和新编译器编译,在同样机器下运行时间不同。
同一个算法程序,用一个老低配置机器和新高配置机器,运行时间也不同。
并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。
那么算法的时间复杂度是一个函数式T(N)
到底是什么呢?这个T(N)
函数式计算了程序的执行次数。
通过c语言编译链接章节学习,我们知道算法程序被编译后生成二进制指令,程序运行,就是cpu执行这 些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)
,假设每句指令执行时间基本一样(实际中有差别,但是微乎其微),那么执行次数和运行时间就是等比正相关,这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。
比如解决一个问题的算法a
程序T(N) = N
,算法b
程序T(N) = N^2
,那么算法a的效率一定优于算法b。
例子:
// 请计算一下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; }
}
分析:
Func1
执行的基本操作次数:
T (N) = N^2^ + 2 ∗ N + 10
N = 10 T(N) = 130
N = 100 T(N) = 10210
N = 1000 T(N) = 1002010
通过对N
取值分析,对结果影响最大的一项是N^2^
实际中我们计算时间复杂度时,计算的也不是程序的精确的执行次数,精确执行次数计算起来还是很麻烦的(不同的一句程序代码,编译出的指令条数都是不一样的),计算出精确的执行次数意义也不大,因为我么计算时间复杂度只是想比较算法程序的增长量级,也就是当N不断变大时T(N)的差别。
上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小,所以我们只需要计算程序能代表增长量级的大概执行次数,复杂度的表示通常使用大O的渐进表示法。
3.1 大O的渐进表示法
大O符号(Big O notation
):是用于描述函数渐进行为的数学符号
推导大O阶规则
时间复杂度函数式
T(N)
中,只保留最高阶项,去掉那些低阶项,因为当N
不断变大时,低阶项对结果影响越来越小,当N
无穷大时,就可以忽略不计了。如果最高阶项存在且不是
1
,则去除这个项目的常数系数,因为当N
不断变大,这个系数对结果影响越来越小,当N
无穷大时,就可以忽略不计了。
T(N)
中如果没有N
相关的项目,只有常数项,用常数1
取代所有加法常数。
通过以上方法,可以得到 Func1
的时间复杂度为:O(N2 )
3.2 时间复杂度计算示例
3.2.1 示例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);
}
Func2
执行的基本操作次数:
F (N) = 2N + 10
Func2
的时间复杂度为:O(N)
3.2.2 示例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);
}
Func3
执行的基本操作次数:
F (N) = M + N
因此:Func3
的时间复杂度为:O(M+N)
3.2.3 示例3
// 计算Func4的时间复杂度?
void Func4(int N)
{ int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count);
}
Func4
执行的基本操作次数:
F (N) = 100
根据推导规则第1条得出
Func4
的时间复杂度为:O(1)
3.2.4 示例4
// 计算strchr的时间复杂度?
const char * strchr ( const char * str, int character)
{const char* p_begin = s;while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;
}
strchr执行的基本操作次数:
若要查找的字符在字符串第一个位置,则:
F (N) = 1
若要查找的字符在字符串最后的一个位置,则:
F (N) = N
若要查找的字符在字符串中间位置,则:
F (N) = N/2
因此:strchr的时间复杂度分为:
最好情况:O(1)
最坏情况:O(N)
平均情况:O(N)
总结:
通过上面我们会发现,有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况
:任意输入规模的最大运行次数(上界)
平均情况
:任意输入规模的期望运行次数
最好情况
:任意输入规模的最小运行次数(下界)大O的渐进表示法在实际中一般情况关注的是算法的上界,也就是最坏运行情况。
3.2.5 示例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; }
}
BubbleSort
执行的基本操作次数:
若数组有序,则:
F (N) = N
若数组有序且为降序,则:
F (N) =[N ∗ (N + 1)] / 2
若要查找的字符在字符串中间位置,则:
因此:BubbleSort
的时间复杂度取最差情况为:O(N2)
3.2.6 示例6
void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}
当n=2时,执行次数为1
当n=4时,执行次数为2
当n=16时,执行次数为4
假设执行次数为x ,则2x = n
因此执行次数:x = log n
因此:func6
的时间复杂度取最差情况为:O(log2n)
注意:
log~2~n 、log n 、 lg n
的表示。当
n
接近无穷大时,底数的大小对结果影响不大。因此,一般情况下不管底数是多少都可以省略不写,即可以表示为log n
不同书籍的表示方式不同,以上写法差别不大,建议使用
log n
3.2.7 示例7
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{ if(0 == N) return 1; return Fac(N-1)*N;
}
调用一次Fac
函数的时间复杂度为O(1)
而在Fac
函数中,存在n
次递归调用Fac
函数
因此:
阶乘递归的时间复杂度为:O(n)
4.空间复杂度
空间复杂度也是一个数学表达式,是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占用了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
4.1 空间复杂度计算示例
4.1.1 示例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; }
}
函数栈帧在编译期间已经确定好了,只需要关注函数在运行时额外申请的空间。
BubbleSort
额外申请的空间有exchange
等有限个局部变量,使用了常数个额外空间
因此空间复杂度为O(1)
4.1.2 示例2
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{ if(N == 0) return 1; return Fac(N-1)*N;
}
Fac
递归调用了N
次,额外开辟了N
个函数栈帧,每个栈帧使用了常数个空间
因此空间复杂度为:O(N)
5.常见复杂度对比
6.复杂度算法题
6.1 旋转数组
思路1:
时间复杂度 O(n2)
循环K
次将数组所有元素向后移动K
位(代码不通过)
void rotate(int* nums, int numsSize, int k) {while(k--){int end = nums[numsSize-1];for(int i = numsSize - 1;i > 0 ;i--){nums[i] = nums[i-1];}nums[0] = end;}
}
粗略估计:O(K*N) = O(n2)
思路2:
空间复杂度 O(n)
申请新数组空间,先将后k
个数据放到新数组中,再将剩下的数据挪到新数组中
void rotate(int* nums, int numsSize, int k)
{int newArr[numsSize];for (int i = 0; i < numsSize; ++i) {newArr[(i + k) % numsSize] = nums[i];}for (int i = 0; i < numsSize; ++i) {nums[i] = newArr[i];}
}
时间复杂度:O(n+n) = O(2n) = O(n)
空间复杂度:O(n)(因为创建了一个新数组)
思路3:
时间复杂度:O(N)
空间复杂度: O(1)
-
前
n-k
个逆置:4 3 2 1
5 6 7 -
后
k
个逆置 :4 3 2 17 6 5
-
整体逆置 :
5 6 7 1 2 3 4
void reverse(int* nums,int begin,int end)
{while(begin < end){//交换nums里面begin到end区域的数字int tmp = nums[begin];//交换left和right的数据nums[begin] = nums[end];nums[end] = tmp;begin++;end--;}
}void rotate(int* nums, int numsSize, int k)
{k = k%numsSize;reverse(nums,0,numsSize-k-1);//前n-k个逆置reverse(nums,numsSize-k,numsSize-1);//后k个数据逆置reverse(nums,0,numsSize-1);//整体逆置
}
相关文章:

【初阶数据结构】1.算法复杂度
文章目录 1.数据结构前言1.1 数据结构1.2 算法1.3 如何学好数据结构和算法 2.算法效率2.1 复杂度的概念2.2 复杂度的重要性 3.时间复杂度3.1 大O的渐进表示法3.2 时间复杂度计算示例3.2.1 示例13.2.2 示例23.2.3 示例33.2.4 示例43.2.5 示例53.2.6 示例63.2.7 示例7 4.空间复杂…...

(图文详解)小程序AppID申请以及在Hbuilderx中运行
今天小编给大家带来了如何去申请APPID,如果你是小程序的开发者,就必须要这个id。 申请步骤 到小程序注册页面,注册一个小程序账号 微信公众平台 填完信息后提交注册 会在邮箱收到 链接激活账号 确认。邮箱打开链接后,会输入实…...

科技创新引领水利行业升级:深入分析智慧水利解决方案的核心价值,展望其在未来水资源管理中的重要地位与作用
目录 引言 一、智慧水利的概念与内涵 二、智慧水利解决方案的核心价值 1. 精准监测与预警 2. 优化资源配置 3. 智能运维管理 4. 公众参与与决策支持 三、智慧水利在未来水资源管理中的重要地位与作用 1. 推动水利行业转型升级 2. 保障国家水安全 3. 促进生态文明建设…...

ExcelVBA运用Excel的【条件格式】(三)
ExcelVBA运用Excel的【条件格式】(三)前面知识点回顾1. 访问 FormatConditions 集合 Range.FormatConditions2. 添加条件格式 FormatConditions.Add 方法语法表达式。添加 (类型、 运算符、 Expression1、 Expression2)其中 TextOperator:***&am…...

coco数据集格式计算mAP的python脚本
目录 背景说明COCOeval 计算mAPtxt文件转换为coco json 格式自定义数据集标注 背景说明 在完成YOLOv5模型移植,运行在板端后,通常需要衡量板端运行的mAP。 一般需要两个步骤 步骤一:在板端批量运行得到目标检测结果,可保存为yol…...

Linux学习——Linux中无法使用ifconfg命令
Linux学习——Linux中无法使用ifconfg命令? 💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅…...

二分查找3
1. 有序数组中的单一元素(540) 题目描述: 算法原理: 二分查找解题关键就在于去找到数组的二段性,这里数组的二段性是从单个数字a开始出现然后分隔出来的,如果mid落入左半部分那么当mid为偶数时nums[mid1]…...

从零开始学习嵌入式----C语言框架梳理与后期规划
目录 一、环境搭建. 二、见解 三、C语言框架梳理 四、嵌入式学习规划流程图(学习顺序可能有变) 一、环境搭建. C语言是一门编程语言,在学习的时候要准备好环境。我个人比较喜欢用VS,具体怎么安装请百度。学习C语言的时候,切忌…...

ESP32 步进电机精准控制:打造高精度 DIY 写字机器人,实现流畅书写体验
摘要: 想让你的 ESP32 不再仅仅是控制灯光的工具吗? 本文将带你使用 ESP32 开发板、步进电机和简单的机械结构打造一个能够自动写字的机器人。我们将深入浅出地讲解硬件连接、软件代码以及控制逻辑,并提供完整的项目代码和电路图,即使是 Ardu…...

传知代码-图神经网络长对话理解(论文复现)
代码以及视频讲解 本文所涉及所有资源均在传知代码平台可获取 概述 情感识别是人类对话理解的关键任务。随着多模态数据的概念,如语言、声音和面部表情,任务变得更加具有挑战性。作为典型解决方案,利用全局和局部上下文信息来预测对话中每…...

部署前端项目
常见部署方式有:静态托管服务、服务器部署 1. 静态托管服务 使用平台部署代码,比如 GitHub。 | 创建一个仓库,仓库名一般是 yourGithubName.github.io。 | 将打包后的静态文件文件上传到仓库。 | 在“Settings”(选项࿰…...

使用POI实现Excel文件的读取(超详细)
目录 一 导入poi相关的maven坐标 二 实现创建并且写入文件 2.1实现步骤 2.2实现代码 2.3效果展示 编辑 2.4注意 三 实现从Excel文件中读取数据 3.1实现步骤 3.2实现代码 3.3结果展示 一 导入poi相关的maven坐标 <!-- Apache poi --><dependency><gro…...

Debezium系列之:记录一次数据库某张表部分数据未同步到hive表的原因
Debezium系列之:记录一次数据库某张表部分数据未同步到hive表的原因 一、背景二、查找数据丢失流程三、数据丢失原因四、解决方法一、背景 反馈mysql数据库中某张表的数据没有同步到hive中,现在需要排查定位下原因数据丢失一般常见需求排查的方向: 数据是否采集到hdfs上采集…...

爆破器材期刊
《爆破器材》简介 《爆破器材》自1958年创刊以来,深受广大读者喜爱,是中国兵工学会主办的中央级技术刊物,在国内外公开发行,近几年已发行到10个国家和地区。《爆破器材》杂志被美国著名检索机构《化学文摘》(CA&a…...

Nginx Websocket 协议配置支持
前后分离的 Web 架构应用,在开发环境启动是可以直接连接支持 websocket 协议,因为没有中间件做转发处理。 当我们对前端进行编译后,通过 nginx 反向代理访问时,需要在nginx 配置文件中增加一些特定的头信息,让服务端识…...

【生成式对抗网络】GANs在数据生成、艺术创作,以及在增强现实和虚拟现实中的应用
一、GANs在数据生成中的应用 生成对抗网络(Generative Adversarial Networks, GANs)在数据生成领域具有显著的应用价值。GANs通过生成器(Generator)和判别器(Discriminator)两个相互竞争的神经网络&#x…...

大模型面试(三)
这次是某家公司的一个电话面试,问的过程还比较简单直接。 问:我们在大模型开源项目的应用上遇到了什么困难? 这个。。有两个困难,一个是RAG的优化,一开始RAG是比较慢的,而且召回率不高; 后来…...

pycharm中快捷键汇总
Pycarm指令汇总 Ctrl鼠标 单击,能直接查看其用法 Ctrl/ 快速注释 CtrlC 在pycharm的terminal中可以停止运行, 其他的地方可以复制。 CtrlV 粘贴 CtrlA 全选 CtrlP 查看()中需要填写什么参数 Altenter 自动不补全所需要的库...

TCP/IP协议族结构和协议
TCP/IP协议族是互联网及许多其他网络的基础,它由一系列相互关联的协议组成,用于实现网络通信。TCP/IP协议族采用ARPANET参考模型,大致可以分为四个层次:链路层、网络层、传输层和应用层。每个层次都有特定的协议和功能,确保数据能够从一个网络设备传输到另一个网络设备。 …...

大模型一些概念的理解 - 线性层、前向传播、后向传播
文章目录 前言一、线性层1. 什么是线性层?2. 通俗解释3. 示例 二、前向传播1. 什么是前向传播?2. 通俗解释3. 示例 三、后向传播1. 什么是后向传播?2. 通俗解释3. 具体步骤 四、示例五、在 PyTorch 中的后向传播 前言 最近提问里有问到一些名…...

AWS 云安全性:检测 SSH 暴力攻击
由于开源、低成本、可靠性和灵活性等优势,云基础设施主要由基于linux的机器主导,然而,它们也不能幸免于黑客的攻击,从而影响云的安全性。攻击Linux机器最流行的方法之一是通过SSH通道。 什么是 SSH 安全外壳协议(Sec…...

7.9数据结构
思维导图 作业 doubleloop.h #ifndef __DOUBLELOOP_H__ #define __DOUBLELOOP_H__#include <stdio.h> #include <stdlib.h>typedef int datatype; typedef struct node {union{int len;datatype data;};struct node *pri;//前驱指针struct node *next;//后继指针…...

Python 文件操作:打开数据处理的大门
在 Python 的学习之旅中,文件操作是一个非常实用且必不可少的技能。不论是数据分析还是日常的数据处理,良好的文件操作技巧都能让你的编程之路更加顺畅。今天,我将带你走进 Python 文件操作的世界,不仅教你如何读写文件࿰…...

单对以太网连接器多场景应用
单对以太网连接器应用场景概述 单对以太网(Single Pair Ethernet,简称SPE)作为一种新兴的以太网技术,以其独特的优势在多个领域得到了广泛的应用。SPE通过单对电缆进行数据传输,支持高速数据传输,同时还能…...

Python pip的更新问题
你是否也出现了更新pip的情况 1、提示更新pip版本 pip install --upgrade pip2、更新操作,我操作了 pip install --upgrade pip更新了,等啊等。。。 然后就是连接超时,安装失败 3、我不信,我就要更新,我还要使用镜…...

[Linux][Shell][Shell基础] -- [Shebang][特殊符号][变量][父子Shell]详细讲解
目录 0.前置知识1.Shebang2.Linux特殊符号整理3.变量4.环境变量5.父子shell0.概念1.创建进程列表(创建子shell执行命令) 6.内置命令 vs 外置命令 0.前置知识 #用于注释shell脚本语⾔属于⼀种弱类型语⾔:⽆需声明变量类型,直接定义使⽤shell三剑客&#…...

DS200CVMAG1AEB处理器 控制器 模块
DS200CVMAG1AEB特征: 高性能:采用先进的控制算法和高功率IGBT器件,可提供高电流和精确的运动控制。 高精度:采用高分辨率编码器和位置环路技术,位置精度可达0.1μm,适用于各种精密机械应用,如数…...

阈值分割后配合Connection算子和箭头工具快速知道区域的ID并选择指定区域
代码 dev_close_window () read_image (Image, E:/机器视觉学习/海康视觉平台/二期VM视觉学习/二期VM视觉学习/机器视觉程序/标定相机找圆心和焊头修正相机找圆心之算法软件/标定相机找圆心和焊头修正相机找圆心之算法软件/03 标定相机找圆心/S2/1号机/1.bmp) get_image_size …...

【work】AI八股-神经网络相关
Deep-Learning-Interview-Book/docs/深度学习.md at master amusi/Deep-Learning-Interview-Book GitHub 网上相关总结: 小菜鸡写一写基础深度学习的问题(复制大佬的,自己复习用) - 知乎 (zhihu.com) CV面试问题准备持续更新贴 …...

【LeetCode】12. 小张刷题计划
稳住,能赢!没有经验的同学在面试岗位的时候,总是显得手忙脚乱,所以多练习,把技能提升,眼界提升,接着心态放平和,不要慌张,把面试题目读懂读透彻就会大大提升赢的概率。 1…...