【算法时间复杂度】学习记录
最近开算法课,开几篇文章记录一下算法的学习过程。
关于算法的重要性
学习计算机当程序员的话,在编程过程中是绕不开算法这个大矿山的,需要我们慢慢挖掘宝藏。
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。
时间复杂度
先了解一下关于时间复杂度的相关概念:
涉及到代码所用时间,我们可以琢磨把代码跑一遍记录一下起始和结束的时间得出整个算法用时,但是很多情况我们是需要理论分析的,不是上机测试,另外硬件的不同也会导致时间有差异。这时候就出现了一个叫做大O表示法。
算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述。
时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析
常见描述时间复杂度的表达式:
O(1):常量时间
O(n):线性时间
O(log n):对数时间
O(n^2):二次方时间
O(2^n):指数时间
O(n!):阶乘时间
常见的算法时间复杂度分析:
O(1)< O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n)
如何计算时间复杂度
O(1)
int func(int n)
{n++;return n*2;
}
上面代码运行时间是一个常量,虽然运行时间是2,但是用O(1)表示,代表时间复杂度是一个常数。
O(n)
int func(int n)
{int sum = 0;for(int i=0; i<n; i++){sum = sum + i;}return sum;
}
上面程序我们分析函数的执行时间是随着n的变化成线性关系:n+2,用O(n)表示线性。
O(n^2 )
int func(int n)
{int sum = 0;for(int i=0; i<n; i++){for(int j=0; j<n; j++){sum = sum + i + j;}}return sum;
}
上面的程序是两层循环的程序,函数的执行时间是n的2次方关系:n^2+2 ,用O(n^2 )来表示时间复杂度。(关于为什么可以省去低幂的我们下面会说明)
O(2^n)
O(2^n)表示指数复杂度,随着n的增加,算法的执行时间成倍增加,它是一种爆炸式增长的情况。
int func(int n)
{if(n==0) return 1;return func(n) + func(n-1)
}
O(log n)
O(log n)表示对数时间复杂度,算法执行时间和n是一种对数关系。这种类型的算法会在执行的过程中,随着程序的执行其完成某个功能的操作步骤越来越少。 其中,我们所熟知的二分查找法就是一个很好的例子。比如,下面这个代码在一个有序列表中查找某个值的位置,我们通过二分法进行查找。
int func(int a[], int size, int num)
{int left = 0;int right = size-1;while(left <= right){int mid = (left + right)/2;if(a[mid] > num){right = mid - 1;}else if (a[mid] < num){left = mid + 1;}else{return num;}}return -1;
}
O(n!)
这个我不是很了解,找一个网上的例子来说说吧。
旅行商问题
假设有一个旅行商人要拜访n+1个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。
常见算法的时间复杂度
相关文章:

【算法时间复杂度】学习记录
最近开算法课,开几篇文章记录一下算法的学习过程。 关于算法的重要性 学习计算机当程序员的话,在编程过程中是绕不开算法这个大矿山的,需要我们慢慢挖掘宝藏。 算法(Algorithm)是指用来操作数据、解决程序问题的一组…...
汽车车机芯片Linux系统内核编译问题总结
谈到车机,很多人会想到华为问界上装的大屏车机,号称车机的天花板,基于鸿蒙OS的,而今天谈到的车机芯片用的是linux内核Kernel,对于它的编译,很多人一时会觉得头大,的确如果工具不是很齐全,就会遇到这样那样的问题,但是过程都会有错误提示,按照错误提示基本可以解决,而…...
Android13 音量曲线调整
Android13 音量曲线调整 Android13 上配置文件的路径: /vendor/sprd/modules/audio/engineconfigurable_apm/工程目录/system/etc/audio_engine_config/audio_policy_engine_stream_volumes.xml /vendor/sprd/modules/audio/engineconfigurable_apm/工程目录/sys…...

OpenHarmony通过MQTT连接 “改版后的华为IoT平台”
一、前言 本篇文章我们使用的是BearPi-HM_Nano开发板:小熊派的主板+E53_IA1扩展板 源码用的是D6_iot_cloud_oc,点击下载BearPi-HM_Nano全量源码 那么为什么要写这篇呢? 前段时间看到OpenHarmony群里,经常有小伙伴问接入华为IoT平台的问题,他们无法正常连接到华为IoT平台等…...

SQS (Simple Queue Service)简介
mazon Simple Queue Service (SQS)是一种完全托管的消息队列服务,可以让你分离和扩展微服务、分布式系统和无服务应用程序。 在讲解SQS之前,首先让我们了解一下什么是消息队列。 消息队列 还是举一个电商的例子,一个用户在电商网站下单后付…...
高速PCB设计指南系列(三)
第一篇 高密度(HD)电路的设计 本文介绍,许多人把芯片规模的BGA封装看作是由便携式电子产品所需的空间限制的一个可行的解决方案,它同时满足这些产品更高功能与性能的要求。为便携式产品的高密度电路设计应该为装配工艺…...

【C++】C++11——左右值|右值引用|移动语义|完美转发
文章目录一、左值与右值1.概念2.引用3.注意二、右值引用的意义1.左值引用意义2.右值引用和移动语义3.容器新增三、万能引用四、完美转发一、左值与右值 1.概念 左值是什么?右值是什么? 左值是一个表示数据的表达式(如变量名或解引用的指针&…...

[ROC-RK3399-PC Pro] 手把手教你移植主线Buildroot(基于2023.02-rc3版本)
🍇 博主主页:Systemcall小酒屋🍇 博主简介:Neutionwei,C站嵌入式领域新星创作者之一,一枚热爱开源技术、喜欢分享技术心得的极客,注重简约风格,热衷于用简单的案例讲述复杂的技术&am…...
重温线性代数
前言 对于普通的数学工作者而言,掌握矩阵、线性空间的基本性质和用法比领会抽象的概念更实用。数学专业的同学需要全面深入学习近世代数的理论和演绎法则,例如模的概念和运算。 总之,我个人认为,不论是微积分、还是线性代数&…...

2023河北沃克HEGERLS甘肃金昌重型仓储项目案例|托盘式四向穿梭车智能密集存储系统在工业行业的创新应用
项目名称:自动化仓储托盘式四向穿梭车智能密集立体库项目 项目合作客户:甘肃省金昌市某集团企业 项目施工地域:甘肃省金昌市 设计与承建单位:河北沃克金属制品有限公司(自主品牌:海格里斯HEGERLS&#x…...

软件测试的案例分析 - 闰年5
文章目的 显示不同的博客能获得多少博客质量分 (这是关于博客质量分的测试 https://www.csdn.net/qc) 这个博客得了 83 分。怎么才能得到更多分数? 正文 我们谈了不少测试的名词, 软件是人写的, 测试计划和测试用例也是人写的, 人总会犯错误。错误发生…...

Linux文件基础I/O
文件IO文件的常识基础IO为什么要学习操作系统的文件操作C语言对于函数接口的使用接口函数介绍如何理解文件文件描述符重定向更新给模拟实现的shell增加重定向功能为什么linux下一切皆文件?文件的常识 1.空文件也要在磁盘占据空间 2.文件 内容 属性 3.文件操作 对…...

HTML看这一篇就够啦,HTML基础大全,可用于快速回顾知识,面试首选
HTML 1 基础 1.1 DOCTYPE <!DOCTYPE> 文档类型声明,作用就是告诉浏览器使用哪种HTML版本来显示网页。 <!DOCTYPE html> 这句代码的意思是: 当前页面采取的是 HTML5 版本来显示网页. 注意: 声明位于文档中的最前面的位置,处于 标签之前。 …...

Altium Designer(AD)软件使用记录05-PCB叠层设计
目录Altium Designer(AD)软件使用记录05-PCB叠层设计一、正片层和负片层的介绍1、正片层(Signal)2、负片层(Plane)3、内电层的分割实现二、正片层和负片层的内缩设计1、负片设置内缩20H原则2、正片铺铜设置内缩1、设置规则2、重新铺铜三、AD的层叠设计四、叠层设计需要注意的问…...

ArcGIS动态表格批量出图
一.产品介绍:ArcGIS动态表格扩展模块Mapping and Charting Solutions,可用于插入动态表格,与数据驱动结合,出图效率无敌。注:优先选择arcgis10.2.2。 二、下载连接: https://www.xsoftnet.com/share/a001CX…...

ChatGPT真神奇,但是也真焦虑
ChatGPT火爆ChatGPT的火爆程度不用说也知道。就目前来说,已经开始冲击各行业了,比如客服、智能助手、语言学习、自然语言处理等等等。。ChatGPT冲击冲击最高的可能就是中间这个段位的了。高段位无法取代,但是低段位,通过使用ChatG…...

mos管驱动与米勒平台介绍、消除
mos驱动设计 1.选择适当的驱动芯片 为了控制MOSFET,需要使用专门的驱动芯片。选择合适的芯片需要考虑MOSFET的电压和电流需求。常见的驱动芯片包括IR2110、IR2184、MIC4424等。 2.设计电路 在驱动电路中,需要加入一些电路元件来保证MOSFET的顺畅工作…...

20230311英语学习
Philosophy of Food: Guidelines for an Authentic Approach to Eating 饮食哲学:值得思考的问题 Whats Philosophical About Food? Philosophy of food finds its basis on the idea that food is a mirror.Eating mirrors the making of a self, that is, the …...
【面试题】Nginx面试题汇总(无解答)
什么是Nginx?谈谈个人都理解,项目中是否用到,为什么要用,有什么优点?为什么要用Nginx?为什么Nginx性能这么高?Nginx怎么处理请求的?什么是正向代理和反向代理?使用“反向…...

Java面试总结(六)
进程和线程的区别 根本区别: 进程时操作系统资源分配的基本单位,而线程是处理器任务调度和执行的基本单位。 资源开销: 每个进程都有自己独立的代码和数据空间(程序上下文),进程之间的切换开销比较大&…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...