02 时间复杂度和空间复杂度

目录

  1. 算法效率
  2. 时间复杂度
  3. 空间复杂度
  4. 练习

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之间的数学表达式,就是该算法的时间复杂度

//计算一下++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);

Func1执行的基本次数:

首先有两个for循环,就是N的平方次,下面的for循环次数是2*N,最后的while循环,次数固定是10

   F(N) = N2 + 2 * N + 10

  • N = 10 F(N) = 130
  • N =100 F(N) = 10210
  • N=1000 F(N) = 1002010
  • 实际中计算时间复杂度时,并不一定要一定要精确的执行次数,只需要大概执行次数,这个就是大O的渐进表示法

2.2 大O的渐进表示法

大O符号(Big O notation):用来描述函数渐进行为的数学符号

推导大O阶的方法:

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

当影响执行次数的变量特别大时,常数的影响微乎其微,时间复杂度只描述最高阶,同样,数量越大,1次方的影响和二次方比越来越小,常数系数也可以省略

这样,大O表示Func1的时间复杂度:

O(N^2^)
  • N = 10 F(N) = 100
  • N = 100 F(N) = 10000
  • N = 1000 F(N) = 1000000

大O渐进法去掉了对结果影响不大的项,简明表示出了执行次数

另外有些算法存在三种情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(上界)

例如找一个数据:
最好情况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 * N + 10 次,大O表示为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);
}

实际执行了M + N次,有两个未知数,所以为O(M + N)

例3:

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

实际执行100次,时间复杂度O(1),表示常数次

例4:

// 计算strchr的时间复杂度?
const char* strchr(const char* str, int character);

最好情况: 第一次就找到
平均情况: character/2
最坏情况: character次找到或未找到

时间复杂度为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;}
}

第一次执行end-1次
第二次执行end-2次
。。。
一直到执行1次

这是一个等差数列,求和 N(1 + N ) /2,大O结果为 O(N2)

例6:

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;
}

二分查找,每找一次,数据集就会缩小当前的一半
第一次需要找N次
第二次需要找N/2次
第三次需要找N/2/2次
。。。
当数据集只剩1个时,就有了结果
假设找了x次,2x = N ,结果就是log2N

时间复杂度O(logN)

logN是优于N的,和折纸相似,可以将数据集扩大看看两者的差距
在这里插入图片描述当14亿数据集时,二分查找最多只需要31次就可以找到

例7:

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

第一次递归Fac(N-1)
第二次递归Fac(N-2)
。。。
最后到Fac(0)

时间复杂度为O(N)

例8:

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

在这里插入图片描述
每一次都需要递归两个函数,公式为
F(n) = 20 + 21 + … 2(n-2)
2F(n) = 21 + 22 + … 2(n-2) + 2(n-1)

用错位相减法,可以抵消,得
2^(n-1) - 1
保留最高项,O(2n)

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

只有一个变量exchange,所以是O(1)

例2:

// 返回斐波那契数列的前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个longlong,所以复杂度O(N)

例3:

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

在这里插入图片描述
每次开辟N个函数空间,每个栈帧使用常数个空间,O(N)

类似的,递归计算裴波那切数列的空间复杂度也是O(N)

因为时间是一去不复返的,空间是可以重复利用的,函数开辟的空间可以重复利用,每次只会执行一个函数

void fun1() {int a = 0;printf("%p\n", &a);
}void fun2() {int b = 0;printf("%p\n", &b);
}

在这里插入图片描述

上面代码,执行后地址是一样的,证明两个函数用的同一份空间

4. 常见复杂度对比

5201314O(1)常数阶
3n+4O(n)线性阶
3n2+4n+5O(n2)平方阶
3log(2)n+4O(logn)对数阶
2n+3nlog(2)+14O(nlogn)nlogn阶
n3+2n2+4n+6O(n3)立方阶
2nO(2n)指数阶

在这里插入图片描述

5. 复杂度练习

在这里插入图片描述
第一种:
排序后,依次查找,如果下一个数不是上一个数加1,就找到了这个数

时间复杂度最好的情况是O(N*logN)

第二种:
将数组内所有数异或,再异或数组长度内每个数,就可以找到这个数

时间复杂度O(N)

int ary[] = { 9, 6, 4, 2, 3, 5, 7, 0, 1 };
int len = sizeof(ary) / sizeof(ary[0]);
int x = 0;for (int i = 0; i < len; i++)
{x ^= ary[i];
}for (int i = 0; i < len + 1; i++)
{x = x ^ i;
}printf("%d", x);

第三种:
0-N等差数列公式求和,减去数组每个值
时间复杂度O(N)

int x = len * (len + 1) / 2;for (int i = 0; i < len; i++)
{x -= ary[i];
}printf("%d", x);

在这里插入图片描述
第一种:
暴力求解,旋转k次
在这里插入图片描述
时间复杂度:O(N2)
空间复杂度: O(1)

第二种:
三段逆置
在这里插入图片描述

void Reverse(int ary[], int left, int right)
{while (left < right){int temp = ary[left];ary[left] = ary[right];ary[right] = temp;left++;right--;}
}void Rotate(int ary[], int len, int k)
{if (k > len)k %= k;Reverse(ary, 0, len - k - 1);Reverse(ary, len - k, len - 1);Reverse(ary, 0, len - 1);
}int nums[] = { 1, 2, 3, 4, 5, 6, 7 };
int len = 7;
int k = 3;
Rotate(nums, 7, k);
for (int i = 0; i < len; i++)
{printf("%d ",nums[i]);
}

时间复杂度: O(N)
空间复杂度: O(1)

第三种:
空间换时间
在这里插入图片描述轮转3个,先把后面的5,6,7放到新数组里,再把前面的拼上

void Rev(int ary[], int len, int k)
{if (k > len)k %= k;int* p = (int*)malloc(len * sizeof(int));memcpy(p, ary + len - k, sizeof(int) * k);memcpy(p + k, ary, sizeof(int) * (len - k));memcpy(ary, p, sizeof(int) * len);free (p);p = NULL;
}

时间复杂度:O(N)
空间复杂度: O(N)

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

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

相关文章

高效学习新编程语言的实践指南

学习一门新的编程语言或框架对于新手和有经验的程序员来说都是一个挑战。然而&#xff0c;通过采用一些有效的策略和方法&#xff0c;我们可以快速入门并掌握新的编程工具。本文将从新手和有编程经验两个不同的角度&#xff0c;分享一些实用的建议和技巧&#xff0c;帮助读者在…

mysql进阶-索引基础

目录 1. 概念-索引是什么&#xff1f; 2. 索引的数据结构(索引模型) 2.1 二分查找&#xff1a; 2.2 二叉查找树&#xff08;BST Binary Search Tree&#xff09;&#xff1a; 2.3 平衡二叉树(AVL Tree Balanced binary search trees) 2.4 多路平衡查找树(B Tree Balanced…

SG-8101CGA 系列 (晶体振荡器 可编程 可用 +125°C )

SG-8101CGA是可编程晶体振荡器&#xff0c;具有CMOS输出&#xff0c;适用于汽车&#xff0c;同时&#xff0c;该系列还提供相同的频率和其他参数的轻松编程能力&#xff0c;符合AEC-Q100标准&#xff0c;具有出色的电磁兼容性和稳定性&#xff0c;可以在各种环境下使用。外部尺…

第六站:C++面向对象

面向对象的第一概念:类 类的构成: “类”&#xff0c;是一种特殊的“数据类型”&#xff0c;不是一个具体的数据。 类的设计: 创建一个类: class Human { public://公有的,对外的void eat();//方法,成员函数void sleep();void play();void work();string getName();//获取对内…

【GitHub项目推荐--克隆你的声音】【转载】

今天推荐一个黑科技开源项目&#xff0c;只需要你 5 秒钟的声音对话&#xff0c;就能克隆出你的声音&#xff0c;而且能够实时的生成你任意语音。 是不是很顶&#xff1f; 我举个例子&#xff0c;如果我这里有 300 条你说话的语音&#xff0c;我把你的语音数据用这个开源项目…

c++ 开发生态环境、工作流程、生命周期-拾遗

拾遗 1 生态环境初识 当您使用Visual Studio 2019进行C开发时&#xff0c;您将进入C生态环境。以下是一些重要的概念和步骤&#xff1a; C程序的结构&#xff1a; 一个典型的C程序包括源文件&#xff08;.cpp&#xff09;、头文件&#xff08;.h&#xff09;、编译后的目标文…

Java 并发性和多线程3

七、线程安全及不可变性 当多个线程同时访问同一个资源&#xff0c;并且其中的一个或者多个线程对这个资源进行了写操作&#xff0c;才会产生竞态条件。多个线程同时读同一个资源不会产生竞态条件。 我们可以通过创建不可变的共享对象来保证对象在线程间共享时不会被修改&…

实战之-Redis代替session实现用户登录

一、设计key的结构 首先我们要思考一下利用redis来存储数据&#xff0c;那么到底使用哪种结构呢&#xff1f;由于存入的数据比较简单&#xff0c;我们可以考虑使用String&#xff0c;或者是使用哈希&#xff0c;如下图&#xff0c;如果使用String&#xff0c;注意他的value&…

AI老照片修复-Bringing-Old-Photos-Back-to-Life

&#x1f3e1; 个人主页&#xff1a;IT贫道-CSDN博客 &#x1f6a9; 私聊博主&#xff1a;私聊博主加WX好友&#xff0c;获取更多资料哦~ &#x1f514; 博主个人B栈地址&#xff1a;豹哥教你学编程的个人空间-豹哥教你学编程个人主页-哔哩哔哩视频 目录 1. AI老照片修复原理-…

第18课 移植FFmpeg和openCV到Android环境

要在Android下从事音视频开发&#xff0c;同样也绕不开ffmpegopencv&#xff0c;不管是初学者还是有一定经验的程序&#xff0c;面临的首要问题就是环境的搭建和库文件的编译配置等问题&#xff0c;特别是初学者&#xff0c;往往会在实际开发前浪费大量的时间来编译ffmpeg及ope…

nvm管理多版本Node.js

nvm管理多版本Node.js 可能大家都曾苦恼于Node环境问题&#xff0c;某个项目需要升版本&#xff0c;某项目又需要降&#xff0c;甚至还出现npm版本与Node对不上的情况。 通过nvm进行版本管理&#xff0c;即可解决。 卸载Node 通过命令行输入node -v命令查看是否已安装Node&…

认知觉醒(九)

认知觉醒(九) 专注力——情绪和智慧的交叉地带 第一节 情绪专注&#xff1a;一招提振你的注意力 用元认知来观察自己的注意力是一件很有意思的事情&#xff0c;相信你可以轻易观察到这种现象&#xff1a;身体做着A&#xff0c;脑子却想着B。 跑步的时候&#xff0c;手脚在…

10.9.2 std::function 存储函数对象 Page184

41行&#xff0c;pending只是inc的复制品&#xff0c;所以43&#xff0c;44行&#xff0c;不会改变inc()的值 demo_function2()的运行结果&#xff1a; 59行&#xff0c;pending是inc的引用&#xff0c;所以61,62行将会改变inc()的值

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK实现相机的高速图像保存(C++)

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK实现相机的高速图像保存&#xff08;C&#xff09;&#xff09; Baumer工业相机Baumer工业相机的图像高速保存的技术背景Baumer工业相机通过NEOAPI SDK函数图像高速保存在NEOAPI SDK里实现线程高速图像保存&#xff1a;工业相机高…

Vue-13、Vue绑定css样式

1、绑定css样式字符串写法&#xff0c;适用于&#xff1a;样式的类名不确定 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>绑定css样式</title><!--引入vue--><script type"tex…

2024三掌柜赠书活动第三期:Rust系统编程

目录 前言 Rust语言概念 关于《Rust系统编程》 Rust系统编程的核心点 Rust系统编程的关键技术和工具 编辑推荐 内容简介 作者简介 图书目录 书中前言/序言 《Rust系统编程》全书速览 结束语 前言 在技术圈&#xff0c;最近的编程语言新秀当属Rust莫属&#xff0c;R…

Java Swing 图书借阅系统 窗体项目 期末课程设计 窗体设计

视频教程&#xff1a; 【课程设计】图书借阅系统 功能描述&#xff1a; 图书管理系统有三个角色&#xff0c;系统管理员、图书管理员、借阅者&#xff1b; 系统管理员可以添加借阅用户&#xff1b; ​图书管理员可以添加图书&#xff0c;操作图书借阅和归还&#xff1b; 借…

希尔排序和计数排序

&#x1f4d1;前言 本文主要是【排序】——希尔排序、计数排序的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1f304;每日一句…

ElasticSearch(1):Elastic Stack简介

1 简介 ELK是一个免费开源的日志分析架构技术栈总称&#xff0c;官网https://www.elastic.co/cn。包含三大基础组件&#xff0c;分别是Elasticsearch、Logstash、Kibana。但实际上ELK不仅仅适用于日志分析&#xff0c;它还可以支持其它任何数据搜索、分析和收集的场景&#xf…