时间复杂度空间复杂度 力扣:转轮数组,消失的数字

news/2024/5/20 20:41:24

1. 算法效率

  1. 如何衡量一个算法的好坏?
  2. 一般是从时间和空间的维度来讨论复杂度,但是现在由于计算机行业发展迅速,所以现在并不怎么在乎空间复杂度了
  3. 下面例子中,斐波那契看上去很简洁,但是复杂度未必如此
long long Fib(int N){if(N < 3)return 1;return Fib(N-1) + Fib(N-2);}
  1. 摩尔定律,每两年硬件性能就会翻两倍,但是现在这个结论有些失效了,主要是因为计算机行业现在快处于瓶颈期了,很难再有突破
  2. 学习复杂度有什么用呢?
    1. 主要是在面试中和校招中考察。
    2. 其实再写一个算法的时候可以进行大概的估算

2. 时间复杂度

  1. 算法的时间复杂度是一个数学函数,定量描述了该算法的运行时间
  2. 每个机器的运行速度都不一样,不同的机器跑一样的代码,时间上会有差异
  3. 所以这个时候有了时间复杂度,时间复杂度计算的是程序执行的次数(大概的次数)
  4. 下面举个最简单的例子,下面代码的复杂度是多少?看时间复杂度,循环嵌套循环的复杂度就是 N^2
  5. 这个得出N^2,是因为在程序执行的时候,假设每执行100次,100次里的第一个循环就要执行100次,外层循环每次执行一次,里面的for循环就要执行100次
int main()
{int n = 100000,count = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){count++;}}printf("%d", count);return 0;
}

2.1. 大0的渐进表示法

  1. 看下面图来说,当 N 值越来越大的时候,2 * N + 10的部分影响就很小了

  1. 因为计算机运行的速度很快,比如我这个电脑运行速度是3.10GHz,也就意味着,在一段时间周期内可以处理3.1亿次指令,对于电脑来说多处理十几万的次数可谓相当轻松。
  2. 大O渐进法,就是对影响结果最大的值进行估算,只要保留最高项就行
  3. 再举个例子 1.N^2 + 2n; 2.N + 100; 3. N^3 。当N在10和100像这种比较小的数的时候,此时他们时间复杂度是差不多的。

2.2. clock 函数 <time.h>

  1. 返回程序消耗的处理器时间 ,单位 毫秒(ms)。
  2. 我的电脑,处理10亿次指令,用2075ms,2秒多。大家有兴趣,也可以用这个函数去试试

2.3. 例题

  1. 0 ms表示,运行时间小于1 ms
  2. 那么下面的时间复杂度是多少呢?时间复杂度计算的是大概的执行次数。是 F(N) = 2 * N + M; 用大O渐进法就是 O(N);
  3. 得出O(N),因为我们要省略对结果影响不大的值
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.3.1. 第二题

  1. 最好的情况就是一方远大于另一方

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

2.3.2. 第三题

  1. 那么这里是多少?,这个O(1), 这里意思不是执行1次,也不是执行时间低于1ms,而是这里的 1,表示常数次(常数就是1,2,3,4,5,...)
void Func4(int N){int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);}

2.4. 大O符号(Big O notation):是用于描述函数渐进行为(大概)的数学符号

  1. 推导大O阶方法:
    1. 用常数1代替运行时的所有加法常数
    2. 去掉其他影响不大的项,只要保留最高阶项
    3. 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
  2. 本质:计算算法复杂度(次数) 属于哪个量级(level)
  3. 假如有两个富豪,一个有2000亿,另一个有3000亿,都去买咖啡喝,不管是便宜的200左右的,还是5000的,就算是50w的。富豪都买的起,意思想表达的就是富豪们都是属于一个级别的你买起,那么他也买的起,这点钱就无足轻重了

常见算法复杂度如下:

2.5. 复杂度的最好、平均和最坏

  1. 最坏情况:任意输入规模的最大运行次数(上限)
  2. 平均情况:输入任意数,期望的运行次数
  3. 最好情况:输入任意数,最小的运行次数(下限)

例如:在长度N的数组中查找一个数据

  1. 最好的情况 O(1),最坏的情况O(N),平均情况 N/2.

2.6. 例题,消失的数字

  1. 此题共提供两种思路
    1. 第1种:用按位或,先按位或上
    2. 第2种:所有项数相加,然后依次减去数组里的值,减去剩下来的值就是,单生狗

//方法1
int missingNumber(int* nums, int numsSize){int one = 0,second = 0;for(int i = 0;i <= numsSize;++i)//numsSize <= 多一个{one ^= i;}for(int j = 0;j < numsSize;j++){second ^= nums[j];}return one ^ second;
}
//方法2
int missingNumber(int* nums, int numsSize){int N = numsSize;//等差数列项数 resultint ret = (0 + N) * (N + 1) / 2; // N + 1 是因为确实的那个项for(int i = 0;i < numsSize; i++){ret -= nums[i];//ret 项数的总和,依次减去数组内的数}return ret;
}
  1. 图中是挨个异或,这里代码中直接先将0 - n,全部异或。然后再异或原数组,最有将两个异或,就得到了这个数

2.7. 轮转数组

  1. 循环条件是 left < right; //不用写 left <= right,当时单数的时候,交不交换都一样。,因为两边向中间靠拢交换
  2. 要画图,画清楚图代码都是水到渠成了
  3. 一定要注意,数组下标绝对不能是负数

void reverse(int* nums,int left, int right)
{while(left < right)//比较的下标值{int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k) {k %= numsSize;// k % numsSize 6 % 7 = 6reverse(nums,0,numsSize - k - 1);reverse(nums,numsSize - k,numsSize - 1);reverse(nums,0,numsSize - 1);
}

2.7.1. 还有一种方法,额外开辟空间

  1. 就是你们常说的用空间换时间,这个的空间复杂度是O(N),为什么是N,因为malloc开辟的空间是未知的
  2. 只要根据上面画的图,稍微推断一下就知道了
  3. 如果还不知道memcpy怎么使用的可以去看看 ,这篇博客C语言的内存函数
void rotate(int* nums, int numsSize, int k) {k %= numsSize;int* numsby = (int*)malloc(sizeof(int) * numsSize);//拷贝到新空间的前三个memcpy(numsby,nums + (numsSize - k),sizeof(int) * k);//把剩下的拷贝memcpy(numsby + k,nums,sizeof(int) * (numsSize - k));//把新空间的拷贝会numsmemcpy(nums,numsby,sizeof(int) * numsSize);free(numsby);numsby = NULL;
}

2.8. logN复杂度

int main()
{int n = 8;int count = 0, i = 1;for (i = 1; i < n; i *= 2){count++;}printf("%d\n", count);return 0;
}
  1. 二分查找的每次区间变化是 N / 2,每次查找都是N /2 /2 /2...
int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);int left = 0, right = sz - 1;int k = 7;while (left <= right)//为啥有等于因为,为单数时还有一个数需要查找{int mid = left + (right - left) / 2;if (arr[mid] < k)//左半没有我需要的值left = mid + 1;else if (arr[mid] > k)//被查找的值小于中间值,此时说明右半区间没有需要的值right = mid - 1;else{printf("%d", mid);break;}left++;right--;}return 0;
}

2.9. 乘阶的复杂度

  1. 乘阶的复杂的是 N + 1,算的是函数的调用次数总和 ,所以就是O(N)。
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N){if(0 == N)return 1;return Fac(N-1)*N;}
  1. 如果乘阶里面还有计算呢?
long long Fac(size_t N){if(0 == N)return 1;for(int i; i < N;i++){;}return Fac(N-1)*N;}
  1. 这个时候每调用一次,for循环就会打印 N次,这个消耗也要算进去,而且这个是递归调用,每次调用自身都会打印 n - 1次的数据,直到满足结束条件。
  2. 所以在这个递归调用里,复杂度是 O(N^2);。所有递归次数累加

2.10. 斐波那契的复杂度

int Fib(int n)
{if (n < 3)return 1;return Fib(n - 1) + Fib(n - 2);
}int main()
{//斐波那契int ret = Fib(40);printf("%d ", ret);return 0;
}
  1. 对此上面的方法只有理论意义,并不具有实际意义
  2. 所以我们要用迭代的方法O(N),来解决,这个方法更好
int main()
{//斐波那契//迭代的方法,因为斐波那契前两项都是1unsigned long long x1 = 1;unsigned long long x2 = 1;unsigned long long x3 = 0;int n = 1150;for (int i = 3; i <= n; i++){x3 = x1 + x2;x1 = x2;x2 = x3;}printf("%lld", x3);return 0;
}
  1. 这种迭代的方法还是不够好,算较小的数还行,数字大了还是不行,会到类型上限
  2. 可以用字符串存储,只要空间够大,多大的数都能存储。不过还没学到,下次一定!!

3. 空间复杂度

  1. 一个算法重点关注时间复杂度,不太关注空间复杂度,除非是嵌入式那些有大小限制的设备上。
  2. 空间复杂度算的是变量的个数,因为每个变量的差异不大,为什么没有什么差异?,举个例子
    1. 1GB = 1024MB;1MB = 1024KB 1 KB = 1024 Byte ;1Byte = 8bit;
    2. 一个MB的空间都有这么大了,还在乎这么点空间吗?
  3. 空间复杂度使用的也是大O渐进法。
  4. 可以来看看实例 ,函数的形参部分的变量不算个数,算的是函数内额外的变量个数
  5. 在此题目中冒泡排序里面,发现只开辟了三个变量,空间复杂度是O(1)
void bbu(int a[], int len)
{for (int i = 0; i < len - 1; i++){for (int j = 0; j < len - i - 1; j++){if (a[j] < a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}
}

3.1. 空间复杂度 O(N)

  1. 实际上空间复杂度比时间复杂度更加容易计算
  2. 常见的空间复杂度只有三个,O(1) O(N) O(N^2);但是也有其他的
  3. 举个空间复杂为O(N)的例子
  4. 每次函数的调用都会创建一个栈帧,创建了多少个栈帧就是多大的空间,会调用N次,O(N)了
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

总结:个人觉得可能会不太详细,但是重点部分都没拉下


http://www.mrgr.cn/p/38473622

相关文章

【JavaEE网络】HTTP响应详解:状态码、报头与正文的全面解析

目录 HTTP响应&#xff08;Response&#xff09;认识 "状态码" (status code)认识响应 “报头”&#xff08;header&#xff09;认识响应 “正文”&#xff08;body&#xff09; HTTP响应&#xff08;Response&#xff09; 响应&#xff1a; 首行响应头空行正文 认…

MySQL#MySql表的操作

目录 一、创建表 二、查看表结构 三、修改表 1.修改表的名字 2.新增一个列 3.修改列 4.删除列 5.修改列的名称 四、删除表 一、创建表 语法&#xff1a; CREATE TABLE table_name (field1 datatype,field2 datatype,field3 datatype ) character set 字符集 collate 校…

一键实现在VS Code中绘制流程图

VS Code是一款常用的IDE&#xff0c;受到许多用户的欢迎和喜爱。而其较为出众的一点&#xff0c;就是较好的可拓展性&#xff0c;即丰富的插件应用&#xff0c;这些应用可以极大地提高生产效率&#xff0c;并优化日常使用。 流程图是一种直观的图示方法&#xff0c;可以用简明…

jsp 实验12 servlet

一、实验目的 掌握怎样在JSP中使用javabean 二、实验项目内容&#xff08;实验题目&#xff09; 编写代码&#xff0c;掌握servlet的用法。【参考课本 上机实验1 】 三、源代码以及执行结果截图&#xff1a; 源代碼&#xff1a; inputVertex.jsp&#xff1a; <% page lang…

[转帖]TLAB(Thread Local Allocation Buffer)

https://www.cnblogs.com/Chary/p/18034613 TLAB是虚拟机在堆内存的eden划分出来的一块专用空间,是线程专属的。在虚拟机的TLAB功能启动的情况下,在线程初始化时,虚拟机会为每个线程分配一块TLAB空间,只给当前线程使用,这样每个线程都单独拥有一个空间,如果需要分配内存,…

【前端】CSS基础(1)

文章目录 前言一、CSS基础1、 CSS是什么2、 CSS基本语法规范3、 代码风格3.1 样式格式3.2 样式大小写3.3 空格规范 4、 CSS引入方式4.1 内部样式表4.2 行内样式表4.3 外部样式 前言 这篇博客仅仅是对CSS的基本结构进行了一些说明&#xff0c;关于CSS的更多讲解以及HTML、Javasc…

YOLOv5改进 | 独家创新篇 | 利用MobileNetV4的UIB模块二次创新C3(全网独家首发)

一、本文介绍 本文给大家带来的改进机制是利用MobileNetV4的UIB模块二次创新C3&#xff0c;其中UIB模块来自2024.5月发布的MobileNetV4网络&#xff0c;其是一种高度优化的神经网络架构&#xff0c;专为移动设备设计。它最新的改动总结主要有两点&#xff0c;采用了通用反向瓶…

OpenHarmony 3.2 Release版本实战开发——Codec HDI适配过程

简介 OpenHarmony Codec HDI&#xff08;Hardware Device Interface&#xff09;驱动框架基于 OpenMax 实现了视屏硬件编解码驱动&#xff0c;提供 Codec 基础能力接口供上层媒体服务调用&#xff0c;包括获取组件编解码能力、创建组件、参数设置、数据的轮转和控制、以及销毁…

GPU通用计算介绍

谈到 GPU &#xff08;Graphics Processing Unit&#xff0c;图形显示卡&#xff09;大多数人想到的是游戏、图形渲染等这些词汇&#xff0c;图形处理确实是 GPU 的一大应用场景。然而人们也早已关注到它在通用计算上的巨大潜力&#xff0c;并提出了 GPGPU (General-purpose co…

Blender动画与云渲染:创造高质量作品的未来路径

Blender作为开源的3D图形软件&#xff0c;在多个领域广受欢迎。但随着项目复杂度提升&#xff0c;传统渲染方式受限。云渲染技术的兴起突破了这些限制&#xff0c;为创作者提供了更自由、高效的创作环境。 一、Blender动画项目的挑战 传统上&#xff0c;Blender动画渲染需要依…

Web安全研究(八)

Good Bot, Bad Bot: Characterizing Automated Browsing Activity S&P 2021 石溪大学 攻击者依赖于恶意的bot发现易受攻击的网站&#xff0c;并入侵服务器泄漏用户数据。因此了解恶意的bot相当重要。 作者设计了Aristaeus&#xff0c;用于部署大量蜜罐网站的系统&#xff…

Android的NDK开发中Cmake报缺少对应的x86的so文件

需要实现一个串口操作的命令。 供应商提供了2个so文件。 分别是 armeabi-v7a 和 arm64-v8a 添加到对应的cpp下。 在CMakeLists.txt里添加so文件 # 添加预编译的库 add_library(libxxx SHARED IMPORTED)# 设置库的路径 set_target_properties(libxxx PROPERTIES IMPORTED_…

C++校招八股

c类的访问权限与继承方式 公有成员在任何地方都可以被访问&#xff0c;包括类的外部和派生类。受保护成员在类的内部和派生类中可以被访问&#xff0c;但在类的外部不可访问。 私有成员只能在类的内部访问&#xff0c;包括类的成员函数和友元函数&#xff0c;不允许在类的外部…

大数据面试题 —— 数据仓库

目录 数据仓库是什么数据仓库和数据库的区别为什么要对数据仓库分层数仓分层&#xff0c;以及每一层的作用维度建模的三种模型范式建模、维度建模维度建模过程&#xff0c;如何确定这些维度 ***维度模型的各个维度之间是怎么聚合的聚合过程的数据倾斜怎么解决&#xff1f;数据质…

【FX110】2024外汇市场中交易量最大的货币对是哪个?

作为最大、最流动的金融市场之一&#xff0c;外汇市场每天的交易量高达几万亿美元&#xff0c;涉及到数百种货币。不同货币对的交易活跃程度并不一样&#xff0c;交易者需要根据货币对各自的特点去进行交易。 全年外汇市场中涉及美元的外汇交易超过50%&#xff01; 实际上&…

基于Vue3与ElementUI Plus的酷企秀场景可视化DIY设计器:前端技术引领下的数字化展示新篇章

一、引言 在当今信息化高速发展的时代&#xff0c;企业对于展示自身形象、提升用户体验以及增强品牌知名度的需求日益迫切。针对这一市场需求&#xff0c;我们推出了基于Vue3与ElementUI Plus的酷企秀场景可视化DIY设计器。该产品不仅具备电子画册、VR全景、地图秀三大核心功能…

MATLAB 三维空间中在两点之间等间隔插入多个点 (67)

MATLAB 三维空间中在两点之间等间隔插入多个点 (67) 一、算法介绍二、算法实现1.代码2.结果一、算法介绍 用于加密直线点云,具体为根据给定的直线端点,沿着该直线方向,插入多个点,从而加密。具体方法和效果如下所示: 二、算法实现 1.代码 代码如下(示例): % 定…

【Qt QML】Frame组件

Frame&#xff08;框架&#xff09;包含在&#xff1a; import QtQuick.Controls继承自Pane控件。用于在可视框架内布局一组逻辑控件。简单来说就是用来包裹和突出显示其他可视元素。Frame不提供自己的布局&#xff0c;但需要自己对元素位置进行设置和定位&#xff0c;例如通过…

C语言leetcode刷题笔记2

C语言leetcode刷题笔记2 第4题&#xff1a;283.移动零互换直接移动 第5题&#xff1a;122.买卖股票的最佳时机‖递归&#xff08;超时&#xff09;动态规划贪心算法 第6题&#xff1a;49.字母异位词分组优化 第4题&#xff1a;283.移动零 给定一个数组 nums&#xff0c;编写一…