【算法篇C++实现】算法的时间、空间复杂度

文章目录

  • 🚀一、算法的概念
  • 🚀二、算法的特征
    • 1.可行性
    • 2.确定性
    • 3.有穷性
    • 4.输入
    • 5.输出
  • 🚀三、算法的评价
    • 1.正确性
    • 2.可读性
    • 3.健壮性
  • 🚀四、算法的复杂度
    • ⛳(一)时间复杂度
      • 1、时间复杂度的概念
      • 2、大O的渐进表示法
      • 3、常见时间复杂度
    • ⛳(二)空间复杂度


🚀一、算法的概念

​ 算法(algorithm)是解决一系列问题的清晰指令,也就是,能对一定规范的输入,在有限的时间内获得所要求的输出。

​ 简单来说,算法就是解决一个问题的具体方法和步骤。算法是程序的灵魂。

程序 = 算法+数据结构

🚀二、算法的特征

1.可行性

​ 算法中执行的任何计算步骤都可以分解为基本可执行的操作步,即每个计算步都可以在有限时间里完成(也称之为有效性)

2.确定性

​ 算法的每一步都要有确切的意义,不能有二义性。例如“增加x的值”,并没有说增加多少,计算机就无法执行明确的运算。

3.有穷性

​ 算法的有穷性是指算法必须在执行有限个步骤后终止。操作次数不宜过大,不能超过人们事先设定的时间限制。

4.输入

算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法已经给出了初始条件。

5.输出

一个算法可能有1个或多个输出,以反映输入数据加工后的代码,没有输出的算法是没有意义的!

🚀三、算法的评价

通常一个好算法应该达到如下目标:

1.正确性

算法应该正确的解决问题。

2.可读性

算法应该具有较好的可读性,让人们理解算法的作用。

3.健壮性

输入非法数据时,算法也可以做出适当的反应,而不会产生奇奇怪怪的输出。

🚀四、算法的复杂度

算法复杂度是指算法在变为可执行程序后所耗费的时间资源和内存。

⛳(一)时间复杂度

1、时间复杂度的概念

评估程序所需要的时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

举例:

Func1 执行的基本操作次数 : F(N) = N^2 + 2*N + 10

当N越来越大的时候,数字的大小主要取决于N^2了。实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i)//这个循环N^2次{for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;} //这个循环2*N次int M = 10;while (M--)  //这个循环10次{++count;}printf("%d\n", count);
}

2、大O的渐进表示法

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后,Func1的时间复杂度为: O(N^2)

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

最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)

例如:在一个长度为N数组中搜索一个数据x

最好情况:1次找到
最坏情况:N次找到
平均情况:N/2次找到

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

3、常见时间复杂度

复杂度标记符号说明
常量O(1)操作数量为常数,与输入数据的规模无关
对数O(log2 n)与输入数据的比例是 log2(n)
线性O(n)与输入数据成正比
平方O(n²)与输入数据规模的比例为平方
立方O(n³)与输入数据规模的比例为立方
指数O(2ⁿ)O(kⁿ)O(n!)快速增长,尽量减少这种代码

代码示范:

实例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*N + 10次,而通过推导大O阶方法,用常数1取代加法常数,得到2*N + 1,只保留最高阶项,得到2*N,将最高阶项的系数变为1,得到N

所以最后的时间复杂度是O(N)

实例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);
}

时间复杂度为O(N+M)

实例3

计算Func4的时间复杂度

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

用常数1替代100,时间复杂度是O(1)

实例4

计算strchr的时间复杂度

const char* strchr(const char* str, int character)
{while (*str != character){str++;}return str;
}

最快执行了1次,最慢执行了N次,所以时间复杂度是O(N)

实例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;}
}

第一趟冒泡排序了N - 1次,第二趟冒泡排序了N - 2次,依次类推,排序这个基本操作在最坏的情况下一共执行了(N-1)+(N-2)+…+3+2+1次比较和交换操作。使用等差数列求和的公式,可以将这个总次数简化为N(N-1)/2。,而最好的情况下是数组已经排好了,此时只需要执行N次,时间复杂度取最坏的情况,所以是O(N^2)

实例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;
}

假如有序数组有N个数,那么查找一次就会将数组的范围缩小一半,直到最后只剩下一个数

可以这么用数字表示:

N / 2 / 2 / 2 / 2 / 2 / 2 … / 2 / 2 = 1

假设查找了x次,也就是每次将数组缩小一半(除以2)这个基本操作执行了x次,那么这个x与N之间的关系是2^x = N

那么x = logN,这里默认底数为2

所以时间复杂度是O(logN)

实例7

计算阶乘递归Fac的时间复杂度

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

基本操作递归了N次,每一层的计算时间复杂度是常数时间。所以时间复杂度为O(N)

实例8

计算斐波那契递归Fib的时间复杂度

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

img

基本操作递归了约为2^N次,根据推到大O阶的方法,所以最后的时间复杂度为O(N)

⛳(二)空间复杂度

  • 空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度
  • 空间复杂度不是程序占用了多少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;}
}

img

可见,红框标注的地方,是在函数的内部额外创建了4个变量,也就是开辟了常数个额外空间,所以空间复杂度为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+1个sizeof(long long)大小的空间,所以空间复杂度为O(N)

实例3

计算阶乘递归Fac的空间复杂度

long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间,所以空间复杂度为O(N)

实例4

计算Fibonacci的空间复杂度

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

每一次递归调用时,每两个子函数用的函数栈帧空间都是同一个,所以只额外开辟了N个栈帧,空间复杂度为O(N)

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

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

相关文章

培训报名小程序报名功能完善

目录 1 修改数据源2 修改表单3 支付成功时修改状态4 创建报名成功页5 最终的效果总结 目前我们的报名功能已经搭建了一个基础版&#xff0c;后续需要展示用户已经报名的信息&#xff0c;需要添加一个状态来显示用户是否成功付费。 1 修改数据源 打开我们的报名数据源&#xff…

使用 Docker 和 Streamlit 构建和部署 LangChain 支持的聊天应用程序

文章目录 前言聊天应用程序组件和技术LangChain Python框架开放人工智能模型前端 Streamlit UI使用 Docker 进行部署Docker 优化以实现轻量级和快速构建Docker-compose.yaml 文件基础设施Streamlit 公共云谷歌应用引擎使用 Google Cloud Run 部署应用1.启动服务2. 创建角色并将…

HDFS中的Trash垃圾桶回收机制

Trash垃圾桶回收机制 文件系统垃圾桶背景功能概述Trash Checkpoint Trash功能开启关闭HDFS集群修改core-site.xml删除文件到trash删除文件跳过从trash中恢复文件清空trash 文件系统垃圾桶背景 回收站&#xff08;垃圾桶&#xff09;是windows操作系统里的一个系统文件夹&#…

Java版企业电子招标采购系统源码—企业战略布局下的采购寻源tbms

​ 项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以…

Jupyter Notebook 未授权访问远程命令执行漏洞

漏洞描述 Jupyter是一个开源的交互式计算环境&#xff0c;它支持多种编程语言&#xff0c;包括Python、R、Julia等。Jupyter的名称来源于三种编程语言的缩写&#xff1a;Ju(lia)、Py(thon)和R。 Jupyter的主要特点是它以笔记本&#xff08;Notebook&#xff09;的形式组织代码…

Effective Java笔记(29)优先考虑泛型

一般来说 &#xff0c;将集合声 明参数化&#xff0c;以及使用 JDK 所提供的泛型方法&#xff0c;这些都不太困难 。编写自己的泛型会比较困难一些&#xff0c;但是值得花些时间去学习如何编写 。 以简单的&#xff08;玩具&#xff09;堆校实现为例 &#xff1a; // Object -…

Android Studio System.out.println()中文乱码

第一步&#xff1a; 打开studio64.exe.vmoptions加入-Dfile.encodingUTF-8 第二步&#xff1a; File-Settings-Editor-File Encodings 把所有的编码格式改为UTF-8 尝试跑一下代码&#xff0c;如果还不行&#xff0c;重启IDE 再试试。

LT8711UXD 是一款高性能双通道 Type-C/DP1.4 至 HDMI2.0 转换器

LT8711UXD 1.描述 LT8711UXD是一款高性能的双车道TypeC/DP1.4到HDMI2.0转换器&#xff0c;设计用于将USB Type-C源或DP1.4源连接到HDMI2.0接收器。LT8711UXD集成了一个DP1.4兼容的接收机&#xff0c;和一个HDMI2.0兼容的发射机。此外&#xff0c;还包括两个CC控制器&#xff0…

在 Linux 上以 All-in-One 模式安装 KubeSphere

官方文档&#xff1a;https://www.kubesphere.io/zh/docs/v3.3/quick-start/all-in-one-on-linux/ 操作系统 最低配置 Ubuntu&#xff1a; 16.04,18.04, 20.04, 22.04 2 核 CPU&#xff0c;4 GB 内存&#xff0c;40 GB 磁盘空间Debian Buste&#xff1a;Stretch 2 核 CPU&am…

前沿分享-无创检测血糖RF波

非侵入性血糖仪&#xff0c;利用射频 (RF) 波连续测量血液中的葡萄糖水平。利用射频波技术连续实时监测血液中的葡萄糖水平&#xff0c;使用的辐射要比手机少得多。 大概原理是血液中的葡萄糖是具有介电特性&#xff0c;一般来说就是介电常数。 电磁波波幅的衰减反映了介质对电…

成功解决Linux下中文乱码问题,CentOS7设置系统字符编码

在linux中&#xff0c;可以使用以下命令查看当前系统的字符编码&#xff1a; echo $LANG 如果不是UTF-8&#xff0c;就会出现中文乱码现象! 解决办法&#xff1a;设置字符编码环境变量为utf-8 1. 打开 ~/.bashrc 或 ~/.bash_profile 文件 vi ~/.bashrc 或 vi ~/.bash_prof…

JAVA Android 正则表达式

正则表达式 正则表达式是对字符串执行模式匹配的技术。 正则表达式匹配流程 private void RegTheory() {// 正则表达式String content "1998年12月8日&#xff0c;第二代Java平台的企业版J2EE发布。1999年6月&#xff0c;Sun公司发布了第二代Java平台(简称为Java2) &qu…

什么是进程、线程、协程

什么是进程&#xff1f; 我们都知道计算机的核心是CPU&#xff0c;它承担了所有的计算任务&#xff1b;而操作系统是计算机的管理者&#xff0c;它负责任务的调度、资源的分配和管理&#xff0c;统领整个计算机硬件&#xff1b;应用程序则是具有某种功能的程序&#xff0c;程序…

IDEA全局设置MyBatis中写SQL语句提示

把这两个设置改成MySQL即可&#xff1a;

IDEA强大的VisualGC插件

前言 开发阶段实时监测&#xff0c;自己的JVM信息&#xff0c;实时可视化 Hotspot JVM 垃圾回收监控工具, 支持查看本地和远程JVM进程, 支持G1 and ZGC算法。 插件安装 在线安装 IntelliJ IDEA 可通过在线安装的方式&#xff0c;安装插件 JDK VisualGC&#xff0c;安装步骤: …

Spring 是如何解决循环依赖问题的?

项目场景&#xff1a; 提示&#xff1a;这里简述项目相关背景&#xff1a; 例如&#xff1a;项目场景&#xff1a;示例:通过蓝牙芯片(HC-05)与手机 APP 通信&#xff0c;每隔 5s 传输一批传感器数据(不是很大) 问题描述 我们都知道&#xff0c;如果在代码中&#xff0c;将两个…

WIN大恒工业相机SDK开发

大恒工业相机SDK开发概览 一、开发环境搭建1、C# 环境配置&#xff08;VS2019&#xff09;2、C 环境配置&#xff08;VS2019&#xff09;3、python 环境配置&#xff08;Pycharm&#xff09; 二、相机二次开发流程三、相机相机属性参数配置四、图像采集单帧采集回调采集 注意事…

65 # 实现 http-server 里的 gzip 压缩

用 zlib 来实现 gzip 压缩 服务端优化都是&#xff1a;压缩 缓存 前端可以通过 webpack 插件进行压缩 gzip 根据替换来实现的&#xff0c;重复率越高&#xff0c;压缩后的结果越小 const zlib require("zlib"); const fs require("fs"); const path …

打开的idea项目maven不生效

方法一&#xff1a;CtrlshiftA&#xff08;或者help---->find action&#xff09;&#xff0c; 输入maven&#xff0c; 点击add maven projects&#xff0c;选择本项目中的pom.xml配置文件&#xff0c;等待加载........ 方法二&#xff1a;view->tools windows->mave…