C++时间复杂度与空间复杂度

一、时间复杂度(Time Complexity)

1. 概念

时间复杂度是用来衡量算法运行时间随着输入规模增长而增长的量级。它主要关注的是算法执行基本操作的次数与输入规模之间的关系,而非具体的运行时间(因为实际运行时间会受硬件、编程语言实现等多种因素影响),旨在从理论上分析算法的效率高低。

2. 大 O 表示法(Big O Notation)

这是描述时间复杂度最常用的方式。它用一个函数来定性描述算法的运行时间与输入规模的关系。例如,对于一个排序算法,如果它的时间复杂度表示为 O(n^2),这意味着随着输入数据量(通常用n表示元素个数等输入规模相关的量)的增加,其运行时间大致按输入规模的平方量级增长。

常见的大 O 表示法的时间复杂度类型有:

  • 常数阶 O(1):无论输入规模n怎么变化,算法执行的基本操作次数是固定的,比如下面这个简单的函数:
int add(int a, int b) {return a + b;
}

这个函数不管传入什么样的整数参数,它都只执行了一次加法操作,基本操作次数恒定,所以时间复杂度是O(1)

  • 线性阶 :基本操作次数与输入规模  成正比。例如,遍历一个长度为  的数组并打印每个元素的操作:
#include <iostream>
void printArray(int arr[], int n) {for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}
}

这里循环会执行n次,随着数组元素个数 n的增多,操作次数线性增长,时间复杂度就是O(n) 。

  • 平方阶 O(n^2):通常出现在嵌套循环中,外层循环执行n次,内层循环对于外层循环的每一次执行也执行 n 次,基本操作次数就是  n×n=n^2次。比如简单的冒泡排序算法的核心代码:
#include <iostream>
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

这里有两层嵌套循环,总的比较和交换操作次数大约是n^2量级,所以时间复杂度是O(n^2) 。

  • 对数阶O(log n) :例如在二分查找算法中,每次查找都会把搜索区间缩小一半,假设数据规模是n ,最多需要查找的次数 k满足n/2^k=1 (也就是最后只剩下一个元素还没确定是否是目标元素的时候停止查找),解这个等式可得k=log2  n ,所以二分查找的时间复杂度是O(log n) (通常省略底数 2,因为不同底数的对数之间只差一个常数系数,在大 O 表示法中可以忽略常数)。示例代码如下:
#include <iostream>
int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}
  • 线性对数阶 O(nlog n):像快速排序、归并排序等高效的排序算法,它们的平均时间复杂度就是O(n log n) 。这些算法在每一层递归或者划分阶段基本操作次数和 n有关,而递归或者划分的层数和 log n 有关,综合起来就是O(n log n)  。以归并排序为例,代码如下:
#include <iostream>
#include <vector>// 合并两个已排序的子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;std::vector<int> L(n1), R(n2);for (int i = 0; i < n1; ++i) {L[i] = arr[left + i];}for (int j = 0; j < n2; ++j) {R[j] = arr[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}while (i < n1) {arr[k++] = L[i++];}while (j < n2) {arr[k++] = R[j++];}
}// 归并排序主函数
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}
3. 计算时间复杂度的步骤
  • 确定算法中的基本操作,比如赋值、比较、算术运算等操作,这些操作执行次数会随着输入规模变化而影响时间复杂度。
  • 分析基本操作执行次数与输入规模  的关系,用数学表达式表示出来,比如是 3n^2+5n+2 这样的式子。
  • 按照大 O 表示法的规则,忽略低阶项(如 5n+2 相对于 3 × n^2 在 n 足够大时影响较小)和常数系数(这里的 3),得到最终的时间复杂度表示,像上面例子就是O(n^2) 。

二、空间复杂度(Space Complexity)

1. 概念

空间复杂度衡量的是算法运行过程中所需要的额外存储空间与输入规模之间的关系。这里强调的是额外存储空间,也就是除了输入数据本身所占空间之外,算法执行过程中临时开辟的空间。

2. 同样用大 O 表示法
  • 常数阶 :算法运行过程中,不管输入规模如何变化,额外开辟的存储空间大小是固定的。例如下面这个函数,只是用了几个固定的变量,没有随输入规模增大而增大的额外空间需求:
int sum(int n) {int result = 0;for (int i = 1; i <= n; ++i) {result += i;}return result;
}

整个函数执行过程中,只开辟了 result 和 i 这两个固定大小的变量空间,所以空间复杂度是 O(1)。

  • 线性阶 O(n):如果算法执行过程中额外开辟的空间和输入规模 n成正比。比如创建一个长度为 n 的数组来存储数据,代码如下:
#include <iostream>
#include <vector>
std::vector<int> createArray(int n) {std::vector<int> arr(n);for (int i = 0; i < n; ++i) {arr[i] = i;}return arr;
}

这里创建的 vector 数组大小取决于输入的参数 n,所以空间复杂度是 O(n)。

  • 平方阶O(n^2) :例如二维数组的情况,当创建一个 n×n 的二维数组时,其元素个数就是 n^2 个,额外空间和 n^2 成正比,空间复杂度就是 O(n^2),示例代码如下:
#include <iostream>
#include <vector>
std::vector<std::vector<int>> createMatrix(int n) {std::vector<std::vector<int>> matrix(n, std::vector<int>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {matrix[i][j] = i * j;}}return matrix;
}
3. 计算空间复杂度的要点
  • 找出算法中随着输入规模变化而动态分配的额外存储空间,像动态申请的数组、递归调用栈等占用的空间。
  • 分析这些额外空间大小与输入规模 n 的数量关系,用大 O 表示法来表示,同样忽略低阶项和常数系数等,得到最终的空间复杂度描述。

总之,在实际的 C++ 编程以及算法设计中,时间复杂度和空间复杂度是衡量算法优劣的重要指标,需要根据具体的应用场景(如对时间要求高还是对空间要求高)来选择合适的算法和数据结构,平衡两者之间的关系。

 

 

 

 

 

 

 

 

 

 

 

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

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

相关文章

【软考】系统架构设计师-信息安全技术基础

信息安全核心知识点 信息安全5要素&#xff1a;机密性、完整性、可用性、可控性、审查性 信息安全范围&#xff1a;设备安全、数据安全、内容安全、行为安全 网络安全 网络安全的隐患体现在&#xff1a;物理安全性、软件安全漏洞、不兼容使用安全漏洞、选择合适的安全哲理 …

SQL Server Management Studio 的JDBC驱动程序和IDEA 连接

一、数据库准备 &#xff08;一&#xff09;启用 TCP/IP 协议 操作入口 首先&#xff0c;我们要找到 SQL Server 配置管理器&#xff0c;操作路径为&#xff1a;通过 “此电脑” 右键选择 “管理”&#xff0c;在弹出的 “计算机管理” 窗口中&#xff0c;找到 “服务和应用程…

类和对象——static 成员,匿名对象(C++)

1.static成员 a&#xff09;⽤static修饰的成员变量&#xff0c;称之为静态成员变量&#xff0c;静态成员变量⼀定要在类外进行初始化。 b&#xff09;静态成员变量为所有类对象所共享&#xff0c;不属于某个具体的对象&#xff0c;不存在对象中&#xff0c;存放在静态区。 …

游戏引擎学习第17天

视频参考:https://www.bilibili.com/video/BV1LPUpYJEXE/ 回顾上一天的内容 1. 整体目标&#xff1a; 处理键盘输入&#xff1a;将键盘输入的处理逻辑从平台特定的代码中分离出来&#xff0c;放入更独立的函数中以便管理。优化消息循环&#xff1a;确保消息循环能够有效处理 …

【JavaEE初阶 — 多线程】线程池

目录 1. 线程池的原理 1.1 为什么要有线程池 1.2 线程池的构造方法 1.3 线程池的核心参数 1.4 TimeUnit 1.5 工作队列的类型 1.6 工厂设计模式 1.6.1 工厂模式概念 1.6.2 使用工厂模式的好处 1.6.3 使用工厂模式的典型案例 1.6.4 Thread…

基于Vue+SpringBoot的求职招聘平台

平台概述 本平台是一个高效、便捷的人才与职位匹配系统&#xff0c;旨在为求职者与招聘者提供一站式服务。平台内设三大核心角色&#xff1a;求职者、招聘者以及超级管理员&#xff0c;每个角色拥有独特的功能模块&#xff0c;确保用户能够轻松完成从信息获取到最终录用的整个…

黑马点评 秒杀下单出现的问题:服务器异常---java.lang.NullPointerException: null(已解决)

前言&#xff1a; 在此之前找了好多资料&#xff0c;查了很多&#xff0c;都没有找到对应解决的方法&#xff0c;虽然知道是userid为空&#xff0c;但不知道要修改哪里&#xff0c;还是自己的debug能力不足&#xff0c;以后得多加练习。。。 问题如下&#xff1a; 点击限时抢…

使用GDB或Delve对已经运行起来的Go程序进行远程调试

同步发布在我的博客&#xff0c;欢迎来点赞。 使用 GDB 或 Delve 对已经运行起来的 Go 程序进行远程调试 使用 GDB 或 Delve 对已经运行起来的 Go 程序进行远程调试 背景 Java 程序可以很方便地通过 jdwp 参数指定一个对外端口进行远程调试&#xff0c;如 java \ -agentlib…

如何解决pdf.js跨域从url动态加载pdf文档

摘要 当我们想用PDF.js从URL加载文档时&#xff0c;将会因遇到跨域问题而中断&#xff0c;且是因为会触发了PDF.js和浏览器的双重CORS block&#xff0c;这篇文章将会介绍&#xff1a;①如何禁用pdf.js的跨域&#xff1f;②如何绕过浏览器的CORS加载URL文件&#xff1f;②如何使…

Jmeter中的断言(三)

9--MD5Hex断言 功能特点 数据完整性验证&#xff1a;验证响应数据的 MD5 哈希值是否符合预期。简单配置&#xff1a;只需提供预期的 MD5 哈希值即可。灵活配置&#xff1a;可以设置多个断言条件&#xff0c;满足复杂的测试需求。 配置步骤 添加 MD5Hex 断言 右键点击需要添加…

Tomcat和Nginx原理说明

Tomcat Tomcat 是一个开源的 Java 应用服务器&#xff0c;它由多个关键组件组成。这些组件共同协作&#xff0c;实现了 Servlet 容器的功能。以下是 Tomcat 的核心组件说明及其逻辑架构的示意图。 1. Tomcat 核心组件说明 (1) Server 描述&#xff1a;Tomcat 的顶级组件&…

vmWare虚拟环境centos7安装Hadoop 伪分布式实践

背景&#xff1a;近期在研发大数据中台&#xff0c;需要研究Hadoop hive 的各种特性&#xff0c;需要搭建一个Hadoop的虚拟环境&#xff0c;本来想着使用dock &#xff0c;但突然发现docker 公共仓库的镜像 被XX 了&#xff0c;无奈重新使用vm 搭建虚拟机。 大概经历了6个小时完…

10 基于深度学习的目标检测

首次完成时间&#xff1a;2024 年 11月 20 日 1. 使用OpenCV的dnn模块实现图像分类。 1&#xff09;程序代码&#xff1a; import numpy as np import cv2# 解析标签文件 row open("model1/synset_words.txt").read().strip().split("\n") class_label …

ssl证书,以 Nginx 为例

文章目录 1 证书概述1.1 常见证书格式1.2 证书的几种扩展名1.3 关于 PKCS#12 格式 2 Nginx 下证书配置2.1 证书的工作原理2.1.1 单向认证2.1.2 双向认证 2.2 CA 机构签发2.2.1 免费 SSL 证书申请2.2.2 双向认证 2.3 自签证书2.3.1 单向认证2.3.2 双向认证 附录 1&#xff1a;Wi…

android:taskAffinity 对Activity退出时跳转的影响

android:taskAffinity 对Activity跳转的影响 概述taskAffinity 的工作机制taskAffinity对 Activity 跳转的影响一个实际的开发问题总结参考 概述 在 Android 开发中&#xff0c;任务栈&#xff08;Task&#xff09;是一个核心概念。它决定了应用程序的 Activity 如何相互交互以…

专家PID控制

专家PID控制&#xff08;Expert PID Control&#xff09;是一种结合了传统PID控制和专家系统思想的控制方法。它通过引入专家经验、规则和推理机制&#xff0c;以改善PID控制器在面对复杂系统时的性能。专家PID控制不仅仅依赖于固定的PID参数&#xff08;比例、积分、微分&…

ES分词环境实战

文章目录 安装下载1.1 下载镜像1.2 单节点启动 防火墙设置异常处理【1】iptable链路中断 参考文档 参加完2024年11月软考&#xff0c;对ES的分词进行考查&#xff0c;前期有【 Docker 环境下安装部署 Elasticsearch 和 kibana】和【 Docker 环境下为 Elasticsearch 安装IK 分…

【桌面应用程序】Vue-Electron 环境构建、打包与测试(Windows)

前言 Vue 与 Electron 环境构建、打包与测试。 目录 前言 一、基本环境准备 二、配置npm源 三、创建Vue项目 四、添加Electron支持 五、应用启动 ​六、添加UI框架 ElementUI ​七、打包 一、基本环境准备 npm版本&#xff1a;8.6.0node版本&#xff1a;v18.0.0Vue/…

golang中的init函数

程序的初始化和执行都起始于 main 包。如果 main 包还导入了其它的包&#xff0c;那么就会在编译时将它们依次 导入。有时一个包会被多个包同时导入&#xff0c;那么它只会被导入一次&#xff08;例如很多包可能都会用到 fmt 包&#xff0c;但 它只会被导入一次&#x…

Paint 学习笔记

目录 ippaint 外扩对象 LCM_inpaint_Outpaint_Comfy&#xff1a; 不支持文字引导 ippaint https://github.com/Sanster/IOPaint 外扩对象 https://www.iopaint.com/models/diffusion/powerpaint_v2 GitHub - open-mmlab/PowerPaint: [ECCV 2024] PowerPaint, a versatile …