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

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.xdnf.cn/news/1410911.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Java -- (part20)

一.Map集合 1.概述 双列集合的顶级接口 2.实现类 HashMap 特点: a.key唯一,value可重复->如果key重复了,会发生value覆盖 b.无序 c.无索引 d.线程不安全 e.可以存null键null值 数据结构: 哈希表 方法: LinkedHashMap 特点: a.key唯一,value可重复->如果ke…

PHP医院安全(不良)事件报告系统源码 vue2+element支持11大类不良事件上报、审核处理、分析改进

PHP医院安全&#xff08;不良&#xff09;事件报告系统源码 vue2element支持11大类不良事件上报、审核处理、分析改进 医院安全&#xff08;不良&#xff09;事件管理系统采用无责的、自愿的填报不良事件方式&#xff0c;有效地减轻医护人员的思想压力&#xff0c;实现以事件为…

深度学习500问——Chapter08:目标检测(6)

文章目录 8.3.7 RetinaNet 8.3.7 RetinaNet 研究背景 Two-Stage 检测器&#xff08;如Faster R-CNN、FPN&#xff09;效果好&#xff0c;但速度相对慢。One-Stage 检测器&#xff08;如YOLO、SSD&#xff09;速度快&#xff0c;但效果一般。 作者对one-stage检测器准确率不高…

QT:label标签的使用

文章目录 设置不同格式的文本显示图片文本对齐/自动换行/缩进/边距 设置不同格式的文本 在文本格式中&#xff0c;存在富文本&#xff0c;makedown格式的文本&#xff0c;还有纯文本&#xff0c;下面就依据这三个进行举例 #include "widget.h" #include "ui_w…

缩小COCO数据集

在运行YOLOS模型的过程中&#xff0c;需要使用到COCO2017这个数据集&#xff0c;但从实验运行来看&#xff0c;其所需时间无疑是相当漫长&#xff0c;预计可能需要近几十天才能完成&#xff0c;因此便考虑缩小COCO数据集大小&#xff0c;即尽可能在遵循其分布的情况下&#xff…

导游讲解口才技巧心得体会总结(3篇)

导游讲解口才技巧心得体会总结&#xff08;3篇&#xff09; **篇&#xff1a;提升表达力&#xff0c;传递独特魅力 在导游工作中&#xff0c;口才技巧的重要性不言而喻。通过不断的实践和反思&#xff0c;我深刻体会到提升表达力对于导游工作的重要性。一个清晰、生动、有趣的…

【c++】继承学习(一):继承机制与基类派生类转换

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本篇文章我们来学习继承部分 目录 1.继承的概念和定义继承的定义继承基类成员的访问方式变化 2.基类和派生类对象赋值转换3.继承中的作用域 1.继承的概念和定义 …

OSPF实验系列---3.综合实验

OSPF的综合实验 实验拓扑及要求如下 实验分析 1.R4为ISP&#xff0c;进行IP配置&#xff0c;区域0为公网区域&#xff0c;配置IP地址 2.做MGRE&#xff0c;R3为中心站点&#xff0c;形成Hub-Spoke 3.子网划分 4.私网互通&#xff0c;NAT转换 5.做特殊区域&#xff0c;修改hel…

【C++】STL简介

&#x1f525;个人主页&#xff1a; Forcible Bug Maker &#x1f525;专栏&#xff1a; C 目录 前言什么是STL&#xff1f;STL的历史STL的版本STL六大组件STL的优缺点STL的优点&#xff1a;STL的缺点&#xff1a; 如何学习STL结语 前言 本篇博客主要内容&#xff1a;STL简介。…

01.本地工作目录、暂存区、本地仓库三者的工作关系

1.持续集成 1.持续集成CI 让产品可以快速迭代&#xff0c;同时还能保持高质量。 简化工作 2.持续交付 交付 3.持续部署 部署 4.持续集成实现的思路 gitjenkins 5.版本控制系统 1.版本控制系统概述2.Git基本概述3.Git基本命令 2.本地工作目录、暂存区、本地仓库三者的工作关系…

AD如何从外部导入外框或修改外框大小

一、从外部导入外框 1、从cad中导出dxf文件&#xff0c;从AD中导入导出的文件 2、可参考如下参数设置 3、导入确认后&#xff0c;选择外边框线&#xff08;选择一条边的线然后按Tab键可快速选择&#xff09; 4、到设计-板子形状中选择“按照选择对象定义” 5、板子外形已经出来…

数字电路-5路呼叫显示电路和8路抢答器电路

本内容涉及两个电路&#xff0c;分别为5路呼叫显示电路和8路抢答器电路&#xff0c;包含Multisim仿真原文件&#xff0c;为掌握FPGA做个铺垫。紫色文字是超链接&#xff0c;点击自动跳转至相关博文。持续更新&#xff0c;原创不易&#xff01; 目录&#xff1a; 一、5路呼叫显…

前端工程化05-初始前端工程化Node基本介绍安装配置基础知识

6、初始前端工程化 6.1、工程化概述 虽然前几篇我的目录标题写的前端工程化&#xff0c;但是那些东西并不属于前端工程化的内容&#xff0c;更倾向于是js、jq当中的东西&#xff0c;下面我们将接触真正的前端工程化。 前端工程化开发其实现在是离不开一个东西的&#xff0c;…

观察者模式实战:解密最热门的设计模式之一

文章目录 前言一、什么是观察者模式二、Java实现观察者模式2.1 观察者接口2.2 具体观察者2.3 基础发布者2.4 具体发布者2.5 消息发送 三、Spring实现观察者模式3.1 定义事件类3.2 具体观察者3.3 具体发布者3.4 消息发送 总结 前言 随着系统的复杂度变高&#xff0c;我们就会采…

文件与IO基础常识知识

在这里&#xff0c;只介绍理论知识&#xff0c;不介绍代码。 目录 1.IO 1.1.字面概念 1.2.输入输出模型 2.文件 2.1.文件目录 2.2.文件路径 2.3.文件分类 1.IO 为了我们接下来学习的文件IO&#xff0c;所以我们先来认识什么是IO。 1.1.字面概念 &#xff08;1&#x…

本地基于知识库的大模型的使用教程

本地基于知识库的大模型的使用教程 启动 双击 大模型启动.bat文件&#xff0c;内容如下&#xff1a; cmd /k "cd /d G:\Anaconda3\Scripts && activate.bat && cd /d D:\docdb_llm && conda activate python3.11 && python startup.py…

MFC 列表控件删除实例(源码下载)

1、本程序基于前期我的博客文章《MFC下拉菜单打钩图标存取实例&#xff08;源码下载) 》 2、程序功能选中列表控件某一项&#xff0c;删除按钮由禁止变为可用&#xff0c;点击删除按钮&#xff0c;选中的项将删除。 3、首先在主界面添加一个删除参数按钮。 4、在myDlg.cpp 文件…

STM32的TIM输入捕获和PWMI详解

系列文章目录 STM32单片机系列专栏 C语言术语和结构总结专栏 文章目录 1. IC输入捕获 2. 频率测量 3. 主模式、从模式、触发源选择 4. 输入捕获基本结构 5. PWMI模式 6. 代码示例 6.1 PWM.c 6.2 PWM.h 6.3 IC.c 6.4 IC.h 6.5 完整工程文件 输出比较可以看下面这篇…

python报错SyntaxError

如果报这个错&#xff0c; 在你的相应的demo.py文件首行输入下面的&#xff0c;可以多试一下&#xff0c;之后就好了。 这个解决方法也是参考其他大佬的做法&#xff0c;不知道为什么python中#是注释&#xff0c;这个也会起作用。 然后就神奇的发现问题解决了。发现下面的代码…

window系统安装MySQL

MySQL的安装和配置 根据不同的系统平台&#xff0c;MySQL由不同安装方式和安装包。 官方下载对应的安装包 官网&#xff1a;www.mysql.com 下载地址&#xff1a;MySQL :: Download MySQL Community Server (Archived Versions) window系统 一、安装包&#xff08;Windows…