数据结构初阶1 时间复杂度和空间复杂度
本章重点
- 算法效率
- 时间复杂度
- 空间复杂度
- 常见时间复杂度以及复杂度OJ练习
1.算法效率
1.1 如何衡量一个算法的好坏
如何衡量一个算法的好坏呢?比如对于以下斐波那契数列:
long long Fib(int N) { if(N < 3) return 1;return Fib(N-1) + Fib(N-2); }
斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何衡量其好与坏呢?
这种递归的斐波那契数列在计算大数字的时候不见得很好用。
这是因为其时间复杂度和空间复杂的原因:
1.2 算法的复杂度
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
##blue##
🔵时间复杂度:主要衡量一个算法的运行快慢,
🔵空间复杂度:主要衡量一个算法运行所需要的额外空间。
在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。
所以我们如今已经不需要再特别关注一个算法的空间复杂度。
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); }
F(N)=N^2+2*N+10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。
像上面的count次数来说,根据数据的慢慢变大N^2更能代表该段程序的时间复杂度
2.2 大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中,只保留最高阶项。
- 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后,上述Func1的时间复杂度为:O(N^2)
- 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:
// 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); }
基本操作执行了2N+10次
通过推导大O阶方法知道,时间复杂度为 O(N)
实例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); }
基本操作执行了M+N次,有两个未知数M和N,
时间复杂度为 O(N)=O(M+N)
两个未知数位阶一样,所以都得留下
实例3:
//3.计算Func4的时间复杂度? void Func4(int N) {int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count); }
基本操作执行了100次,通过推导大O阶方法,时间复杂度为 O(1)
用常数1取代运行时间中的所有加法常数。
O(1)代表的是常数次
这样写其实是因为我们现在电脑的CPU运行的足够快,
这里我们可以写个代买来运行测试一下:
include<time.h> int main() {size_t begin = clock();//引头文件time.h//这个函数是用来记录时间的,到运行它的时候会记录一个时间,单位毫秒size_t n = 0;for (size_t i = 0;i < 1000000000;i++){n++;}size_t end = clock();printf("%d毫秒\n", end - begin);return 0; }
实例4:
//4. 计算strchr的时间复杂度? const char* strchr(const char* str, int character);
这里简单介绍一下strchr函数:
就是在字符串str里面找一个字符character,找不到:str++,找到就返回str地址,
大家也可以去cplusplus.com里面看 strchr()函数的详细解释
如果整个字符串有n个元素,要找其中的一个元素,这个时候就有一下几种情况:
最好:O(1),最坏:O(N),平均:O(N/2)
这个时候我们一般取最坏的情况:O(N)
实例5:冒泡排序的时间复杂度
// 5.计算BubbleSort的时间复杂度? void BubbleSort(int* a, int n) {for (size_t end = n; end > 1; --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;} }
按最坏情况来看:
第一趟冒泡排序是:N-1,第二趟:N-2,第三趟N-3…最后一次是:1
可以看出来是需要进行:N*(N-1)/2 次循环
基本操作执行最好N次,最坏执行了 N * (N-1)/2 次,
通过推导大O阶方法+时间复杂度一般看最坏,时间复杂度为 O(N^2)
实例6:二分查找的时间复杂度
//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;elsereturn mid;}return -1; }
二分法查找:每次查找,查找区间缩小一半,查找多少次,出2多少次
这里可以吧二分法查找想象成折纸,更容易理解一些
基本操作执行最好1次,最坏O(logN)次
(log以2为底的N,不好在计算机上表示,所以会简写为logN,其他底数不能省略)时间复杂度为 O(logN)
实例7:
//7. 计算阶乘递归Fac的时间复杂度? long long Fac(size_t N) {if (0 == N)return 1;return Fac(N - 1) * N; }
现基本操作递归了N次,时间复杂度为 O(N)
实例8:
//8. 计算斐波那契递归Fib的时间复杂度? long long Fib(size_t N) {if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2); }
基本操作递归了2N次,时间复杂度为O(2N)。
像一个细胞分裂一样,n次分裂,就是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;} }
使用了常数个额外空间,所以空间复杂度为 O(1)
实例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; }
动态开辟了N个空间和若干个常数项,所以空间复杂度为 O(N)
实例3:
// 计算阶乘递归Fac的空间复杂度? long long Fac(size_t N) {if (N == 0)return 1;return Fac(N - 1) * N; }
递归调用了N次,开辟了N个栈帧,每次开辟后没有被销毁,
每个栈帧使用了常数个空间。
空间复杂度为O(N)
这里如果使用循环就是O(1)
这里注意时因为空间是可以重复利用的,所以不会对一个数据重复开辟
4.复杂度的oj练习
4.1消失的数字:
消失的数字 - 力扣(LeetCode)
数组nums包含从0到n的所有整数,但其中缺了一个。
请编写代码找出那个缺失的整数(在 O(n) 时间内完成)注意:本题相对书上原题稍作改动示例 1:输入:[3,0,1]
输出:2示例 2:输入:[9,6,4,2,3,5,7,0,1]
输出:8
方法一:公式计算
将数组的大小+1进行累加 减去 将数组中的所有数加起来,即可求得
int main()
{int arr[] = { 9,6,4,2,3,5,7,0,1 };int sz = sizeof(arr) / sizeof(arr[0]);int add1 = 0;int add2 = 0;int i = 0;for (i = 0;i < sz;i++){add1 += arr[i];}for (i = 0;i < sz + 1;i++){add2 += i;}printf("%d\n", add2 - add1);return 0;
}
这里的时间复杂度为O(N)
空间复杂度为O(1)
方法二:异或
将n个数组元素于0~n+1的字符串异或,即可求得
int main()
{int arr[] = { 9,6,4,2,3,5,7,0,1 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;int add = 0;for (i = 0;i < sz;i++){add ^= arr[0];}for (i = 0;i < sz+1;i++){add ^= i;}printf("%d\n", add);return 0;
}
这里的时间复杂度为O(N)
空间复杂度为O(1)
方法三:排序+二分查找
时间复杂度 O(N*logN)
4.2 旋转数组:
轮转数组 - 力扣(LeetCode)
给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入: nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105进阶:
尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
方法一:一个一个的挪
void func1(int *a,int sz,int k)
{for (int i = 0;i < k;i++){int tmp = a[sz-1];for (int j = sz;j > 0;j--){a[j - 1] = a[j - 2];}a[0] = tmp;}
}
int main()
{int k = 0;scanf("%d", &k);int arr[9] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);k %= sz;//方法一://func1(arr,sz,k);for (int i = 0; i < sz;i++){printf("%d ", arr[i]);}printf("\n");return 0;
}
但是这个方法在LeetCode上面编译不过去,因为时间复杂度有点大:O(N+K)
方法二:另一个数组进行存储
牺牲空间去换取时间效率,用另一个数组来进行存储,再复制回去
void func2(int* a, int sz, int k)
{int a2[10] = { 0 };int n = sz - k;int i = 0;int j = 0;for (i;i < n;i++){a2[i] = a[i];}for (j=0;j < k;j++,i++){a2[i] = a[i];}for (j = 0;j < sz;j++){a[j] = a2[j];}
}
int main()
{int k = 0;scanf("%d", &k);int arr[9] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);k %= sz;//方法二:func2(arr, sz, k);for (int i = 0; i < sz;i++){printf("%d ", arr[i]);}printf("\n");return 0;
}
方法三:颠倒数组
void reverse(int* a, int begin, int end)
{while (begin < end){int tmp = a[begin];a[begin] = a[end];a[end] = tmp;++begin;--end;}
}
void func3(int* a, int sz, int k)
{reverse(a, 0, sz - k - 1);reverse(a, sz-k, sz- 1);reverse(a, 0, sz - 1);
}
int main()
{int k = 0;scanf("%d", &k);int arr[9] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);k %= sz;//方法三:func3(arr, sz, k);for (int i = 0; i < sz;i++){printf("%d ", arr[i]);}printf("\n");return 0;
}
相关文章:
数据结构初阶1 时间复杂度和空间复杂度
本章重点 算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度OJ练习 1.算法效率 1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: long long Fib(int N) { if(N < 3) return 1;return Fib(N-1) Fib(N-2); }斐…...

E130 PHP+MYSQL+动漫门户网站的设计与实现 视频网站系统 在线点播视频 源码 配置 文档 全套资料
动漫门户网站 1.摘要2. 开发背景和意义3.项目功能4.界面展示5.源码获取 1.摘要 21世纪是信息的时代,随着信息技术与网络技术的发展,其已经渗透到人们日常生活的方方面面,与人们是日常生活已经建立密不可分的联系。本网站利用Internet网络, M…...

OSCP - Proving Grounds - Fanatastic
主要知识点 CVE-2021-43798漏洞利用 具体步骤 执行nmap 扫描,22/3000/9090端口开放,应该是ssh,grafana 和Prometheus Nmap scan report for 192.168.52.181 Host is up (0.00081s latency). Not shown: 65532 closed tcp ports (reset) PORT STA…...

ArcMap 分享统计点要素、路网、降雨量等功能操作
ArcMap 分享统计点要素、路网等功能等功能操作今天进行 一、按格网统计点要素 1、创建公里网格统计单元 点击确定后展示 打开连接 点击后 展示 2、处理属性 1)查看属性表 每个小格都统计出了点的数量 2)查看属性 符号系统 点击应用后展示结果&#x…...

概率论——假设检验
解题步骤: 1、提出假设H0和H1 2、定类型,摆公式 3、计算统计量和拒绝域 4、定论、总结 Z检验 条件: 对μ进行检验,并且总体方差已知道 例题: 1、假设H0为可以认为是570N,H1为不可以认为是570N 2、Z…...
爬虫项目练手
python抓取优美图库小姐姐图片 整体功能概述 这段 Python 代码定义了一个名为 ImageDownloader 的类,其主要目的是从指定网站(https://www.umei.cc)上按照不同的图片分类,爬取图片并保存到本地相应的文件夹中。不过需要注意&…...
C程序设计:解决Fibonacci.数列问题
‘ 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称“兔子数列”,其数值为:1、1、2、…...

35页PDF | 元数据与数据血缘落地实施(限免下载)
一、前言 这份报告详细介绍了元数据与数据血缘的概念、重要性以及在企业数据中台中的应用。报告阐述了数据中台的核心价值在于整合和管理体系内的数据,以提升数据资产化能力并支持业务决策。报告还涵盖了元数据的分类(技术元数据和业务元数据࿰…...

Lua元表和元方法的使用
元表是一个普通的 Lua 表,包含一组元方法,这些元方法与 Lua 中的事件相关联。事件发生在 Lua 执行某些操作时,例如加法、字符串连接、比较等。元方法是普通的 Lua 函数,在特定事件发生时被调用。 元表包含了以下元方法࿱…...

基于Pyhton的人脸识别(Python 3.12+face_recognition库)
使用Python进行人脸编码和比较 简介 在这个教程中,我们将学习如何使用Python和face_recognition库来加载图像、提取人脸编码,并比较两个人脸是否相似。face_recognition库是一个强大的工具,它基于dlib的深度学习模型,可以轻松实…...
Spring Boot+Netty
因工作中需要给第三方屏幕厂家下发广告,音频,图片等内容,对方提供TCP接口于是我使用Netty长链接进行数据传输 1.添加依赖 <!-- netty依赖--><dependency><groupId>io.netty</groupId><artifactId>netty-all&…...

LCR 023. 相交链表
一.题目: LCR 023. 相交链表 - 力扣(LeetCode) 二.我的原始解法-无: 三.其他人的正确及好的解法,力扣解法参考: 哈希表法及双指针法:LCR 023. 相交链表 - 力扣(LeetCode࿰…...
Linux命令行下载工具
1. curl 1.1. 介绍 curl是一个功能强大的命令行工具,用于在各种网络协议下传输数据。它支持多种协议,包括但不限于 HTTP、HTTPS、FTP、FTPS、SCP、SFTP、SMTP、POP3、IMAP 等,这使得它在网络数据交互场景中有广泛的应用。curl可以模拟浏览器…...
期末复习-Hadoop名词解释+简答题纯享版
目录 一、名称解释(8选5) 1.什么是大数据 2.大数据的5V特征 3.什么是SSH 4.HDFS(p32) 5.名称节点 6.数据节点 7.元数据 8.倒排索引 9.单点故障 10.高可用 11.数据仓库 二、简答题 1.简述Hadoop的优点及其含义 2.简述…...
嵌入式Linux无窗口系统下搭建 Qt 开发环境
嵌入式Linux无窗口系统下搭建 Qt 开发环境 本文将介绍如何在树莓派的嵌入式 Linux 环境下,搭建 Qt 开发环境,实现无窗口系统模式(framebuffer)下的图形程序开发。 1. 安装 Qt 环境 接下来,安装核心 Qt 开发库以及与 …...
C#基础教程
1. C# 基础语法和操作符 C# 中的运算符优先级 namespace OperatorsAppl {class Program7{static void Main(string[] args){int a 20; // 定义变量aint b 10; // 定义变量bint c 15; // 定义变量cint d 5; // 定义变量dint e; // 定义变量e// 演示运算符优先级&…...

Alibaba EasyExcel 导入导出全家桶
一、阿里巴巴EasyExcel的优势 首先说下EasyExcel相对 Apache poi的优势: EasyExcel也是阿里研发在poi基础上做了封装,改进产物。它替开发者做了注解列表解析,表格填充等一系列代码编写工作,并将此抽象成通用和可扩展的框架。相对p…...

Spring Cloud + MyBatis Plus + GraphQL 完整示例
Spring Cloud MyBatis Plus GraphQL 完整示例 1、创建Spring Boot子项目1.1 配置POM,添加必要的依赖1.2 配置MyBatis-Plus 2、集成GraphQL2.1 定义schema.graphqls2.2 添加GraphQL解析器2.3 配置schame文件配置 3、访问测试3.1 查询测试(演示ÿ…...

uni-app简洁的移动端登录注册界面
非常简洁的登录、注册界面模板,使用uni-app编写,直接复制粘贴即可,无任何引用,全部公开。 废话不多说,代码如下: login.vue文件 <template><view class"content"><view class&quo…...

LongVU:用于长视频语言理解的空间时间自适应压缩
晚上闲暇时间看到一种用于长视频语言理解的空间时间自适应压缩机制的研究工作LongVU,主要内容包括: 背景与挑战:多模态大语言模型(MLLMs)在视频理解和分析方面取得了进展,但处理长视频仍受限于LLM的上下文长…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...