【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比
【数据结构与算法——TypeScript】
算法的复杂度分析
什么是算法复杂度(现实案例)?
❤️🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。
✅ 对于同一个问题,我们往往有很多种解决思路和方法,也就是可以采用不同的算法。
-
举个例子(现实例子):在一个庞大的图书馆中,我们需要找一本书
- 在图书已经按照某种方式摆好的情况下(数据结构是固定的)
-
方式一:顺序查找
- 一本一本找,直到找到想要的书;
-
方式二:先分类找,分类中找这本书
- 先找到分类,在分类中再顺序或某种方式查找
-
方式三:找到检索电脑,查找书的位置,直到找到
- 图书馆通常有自己的图书管理系统
- 利用图书管理系统先找到书的位置,再直接过去找到
什么是算法复杂度(程序案例)?
🖥 在具体一个程序中的案例:让我们用两种不同算法查找数组中(数组有序)给定元素的复杂度
- ✅ 方式一:顺序查找
- 这种算法 从头到尾遍历整个数组,依次比较每个元素和给定元素的值
- 如果 找到相等的元素,则返回下标;如果 遍历完整个数组都没找到,则返回 -1。
/**- 顺序查找- @param array 查找的数组- @param 查找的元素- @returns 查找到的索引,未找到返回-1*/function sequentSearch(array: number[], num: number) {for (let i = 0; i < array.length; i++) {const element = array[i];if (element === num) return i;}return -1;}const index = sequentSearch([1, 3, 5, 10, 100, 222, 333, 334, 555, 556], 222);console.log(index);
-
✅ 方式二:二分查找
- 这种算法假设数组是有序的,每次 选择数组中间的元素与给定元素进行比较。
- 如果 相等,则返回下标;如果 给定元素比中间元素小,则在数组的左半部分继续查找;
- 如果 给定元素比中间大,则在数组的右半部分继续查找;
- 这样 每次查找都会将查找范围减半,直到找到想等的元素或者查找范围为空。
function binarySearch(array: number[], num: number) { // 1. 定义左右索引 let left = 0; let right = array.length - 1;// 2.开始查找 while (left <= right) {let mid = Math.floor((left + right) / 2);const midNum = array[mid];if (midNum === num) {return mid;} else if (midNum < num) {left = mid + 1;} else {right = mid - 1;} } return -1; } const index = binarySearch([1, 3, 5, 10, 100, 222, 333, 334, 555, 556], 222); console.log(index); export {};
测试顺序查找和二分查找的代码
- 使用🔧工具:
npm install hy-algokit
import sequentSearch from './01_查找算法-顺序查找';
import binarySearch from './02_查找算法-二分查找';
import { testOrderSearchEfficiency } from 'hy-algokit';
testOrderSearchEfficiency(sequentSearch);
testOrderSearchEfficiency(binarySearch);
-
❤️🔥 顺序查找算法的时间复杂度是
O(n)
-
❤️🔥 二分查找算法的时间复杂度是
O(log n)
大O表示法(Big O notation)
- 大O表示法(Big O notation)英文翻译为大O符号,中文通常翻译为大O表示法(标记法)。
- 大O符号在分析 算法效率的时候非常有用。
- 🌰 举例:解决 **一个规模为n的问题所花费的时间(或需要步骤的数目)可以表示为:
T(n)= 4n⌃2^ - 2n + 2
**- 当
n
增大 时,n^2^
项开始 占据主导地位,其他各项可以被忽略。
- 🌰 : 当
n = 500
-
✓ 4n2 项是 2n 项的 1000倍大,因此在大多数场合下, 省略后者对表达式的值的影响将是乐意忽略不计的。
-
进一步,如果我们与任一其他级的表达式比较, n2的系数也是无关紧要的的。
-
这样,针对第一个例子, T(n)= 4 n2 - 2n + 2,大O符号就记下剩余的部分,写作:
-
T(n) ∈ O(n2)
或者
-
T(n) = O(n2)
-
-
- 🌰 举例:解决 **一个规模为n的问题所花费的时间(或需要步骤的数目)可以表示为:
- ❣️ 我们就说该算法 具有n2 阶(平方阶)的时间复杂度,表示为O(n2)。
常见的对数阶
- 常用的函数阶
符号 | 名称 |
---|---|
O(1) | 常数(阶、下同) |
O(log n) | 对数 |
O(n) | 线性、次线性 |
O(n log n) | 线性对数、或者对数线性、拟线性、超线性 |
O(n2) | 平方 |
O(n2) , Interger(c > 1) | 多项式,有时叫作‘代数’(阶) |
O(cn) | 指数,有时叫作“几何”(阶) |
空间复杂度
-
空间复杂度指的是,程序运行过程中所需要的额外存储空间。
- 空间复杂度 也可以用大O表示法来表示;
- **空间复杂度的计算方法与时间复杂度类似,**通常需要分析程序中 需要额外分配的内存空间,如数组、变量、对象、递归调用等。
-
🌰 :举例
- 对于一个简单的 递归算法来说,每次调用会在内存中分配新的栈帧,这些栈帧占用了额外的空间。
- 因此,该算法的空间复杂度是 O(n),其中n是递归深度
- 而对于 迭代算法来说,在 **每次迭代中不需要分配额外的空间,**因此 其空间复杂度为O(1)
- 对于一个简单的 递归算法来说,每次调用会在内存中分配新的栈帧,这些栈帧占用了额外的空间。
-
当空间复杂度很大时,可能会导致内存不足,程序崩溃。
-
在平时进行算法优化时,我们通常会进行如下考虑:
- 使用尽量少的空间(优化空间复杂度)
- 使用尽量少的时间(优化时间复杂度)
- 特定情况下:使用 空间换时间或使用 时间换空间。
数组和链表的对比
- 使用大O表示法来对比一下数组和链表的时间复杂度(增删改查)
Data Structure | Access | Search | Insertion | Deletion |
---|---|---|---|---|
Array | O(1) | O(N) | O(N) | O(N) |
Linked List | O(N) | O(N) | O(1) | O(1) |
-
数组是一种连续的存储结构,通过下标可以直接访问数组中的任意元素。
- 时间复杂度: 对于数组,随机访问时间复杂度为O(1),插入和删除操作的时间复杂度为O(n)。
- 空间复杂度:数组需要连续的存储空间,空间复杂度为 O(n)
-
链表,是一种链式存储结构,通过指针链接起来的节点组成,访问链表中元素需要从头结点开始遍历
- **时间复杂度:**对于链表,随机访问时间复杂度为O(n),插入和删除的时间复杂度为O(1)
- **空间复杂度:**链表需要为每个节点分配存储空间,空间复杂度为O(n)
-
💖 在实际开发中,选择使用数组还是链表需要根据具体应用场景来决定
- 如果数据量不大,且需要频繁随机访问元素,使用数组可能会更好
- 如果数据量很大,或者需要频繁插入和删除元素,使用链表可能会更好
【数据结构与算法——TypeScript】系列笔记:
1. 【数据结构与算法——TypeScript】数组、栈、队列、链表
相关文章:

【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比
【数据结构与算法——TypeScript】 算法的复杂度分析 什么是算法复杂度(现实案例)? ❤️🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题,我们往往有很多种解决思路和方法&#x…...

搜索综合训练
搜索综合训练 选数详细注释的代码 小木棍详细注释的代码 费解的开关详细注释的代码 选数 详细注释的代码 #include <iostream> #include <vector>using namespace std;// 判断一个数是否为素数 bool isPrime(int num) {if (num < 1)return false;// 判断从2到s…...
snowboy+新一代kaldi(k2-fsa)sherpa-onnx实现离线语音识别【语音助手】
背景 本系列主要目标初步完成一款智能音箱的基础功能,包括语音唤醒、语音识别(语音转文字)、处理用户请求(比如查天气等,主要通过rasa自己定义意图实现)、语音合成(文字转语音)功能。 语音识别、语音合成采用离线方式实现。 语…...

APT80DQ20BG-ASEMI快恢复二极管80A 200V
编辑:ll APT80DQ20BG-ASEMI快恢复二极管80A 200V 型号:APT80DQ20BG 品牌:ASEMI 芯片个数:双芯片 封装:TO-3P 恢复时间:≤50ns 工作温度:-55C~150C 浪涌电流:600A*2 正向电流…...

Go的任务调度单元与并发编程
摘要:本文由葡萄城技术团队于CSDN原创并首发。转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。 前言 本文主要介绍Go语言、进程、线程、协程的出现背景原因以及Go 语言如何解决协程的…...
PDFbox教程_编程入门自学教程_菜鸟教程-免费教程分享
教程简介 PDFBox是一个开源Java库,支持PDF文档的开发和转换.使用此库,您可以开发用于创建,转换和操作PDF文档的Java程序.除此之外,PDFBox还包括一个命令行实用程序,用于使用可用的PDF对PDF执行各种操作Jar文件. PDFB…...
Node.js-模块化理解及基本使用
模块化的定义 讲一个复杂的程序文件按照一定的规则拆分成多个独立的小文件,这些小文件就是小模块,这就是模块化。 每个小模块内部的数据是私有的,可以暴露内部数据给外部其他模块使用。 模块化优点 减少命名的冲突提高复用性提高可维护性按需…...
arguments 和 剩余参数
加油 !! 💕 文章目录 前言一、arguments二、arguments转成array三、箭头函数不绑定arguments四、剩余参数 ... 前言 其实在es6之后不推荐使用 arguments , 建议使用剩余参数 一、arguments arguments 是一个 对应于 传递给函数的参数 的 类数…...
【BASH】回顾与知识点梳理(十二)
【BASH】回顾与知识点梳理 十二 十二. Linux 文件与目录管理12.1 目录与路径相对路径与绝对路径相对路径的用途绝对路径的用途 12.2 目录的相关操作cd (change directory, 变换目录)pwd (Print Working Directory, 显示目前所在的目录)mkdir (make directory, 建立新目录)rmdir…...

本地构建包含java和maven的镜像
目录 1.前提条件 2.下载 2.1.创建Dockerfile 3.构建镜像 参考文章 1.前提条件 本地环境需要的系统和软件 win10 Docker Desktop Powershell 图1 Win10安装Docker后,直接在Powershell使用Docker命令 有些Developer不习惯win10系统,却想要使用Lin…...
Programming abstractions in C阅读笔记:p76-p83
《Programming Abstractions In C》学习第42天,p76-p73总结。 一、技术总结 1.数组和指针 在C语言中,数组和指针非常相似,相似到必须将它们同时考虑,当看到数组就应该想到指针,当看到指针就应该想到数组。示例…...
已解决(三个问题)|neo4j Failed authentication attempt for ‘meter‘ from 127.0.0.1
问题1 py2neo.errors.ConnectionUnavailable: Connection has been closed 问题2 neo4j Failed authentication attempt for ‘meter’ from 127.0.0.1 问题3 py2neo.errors,ClientError: [Security.Unauthorized] Invalid username or password. 作者:xiao黄 博客地址:http…...
neo4j查询语言Cypher详解(二)--Pattern和类型
Patterns 图形模式匹配是Cypher的核心。它是一种用于通过应用声明性模式从图中导航、描述和提取数据的机制。在MATCH子句中,可以使用图模式定义要搜索的数据和要返回的数据。图模式匹配也可以在不使用MATCH子句的情况下在EXISTS、COUNT和COLLECT子查询中使用。 图…...

动态规划(用空间换时间的算法)原理逻辑代码超详细!参考自《算法导论》
动态规划(用空间换时间的算法)-实例说明和用法详解 动态规划(DP)思想实例说明钢条切割问题矩阵链乘法问题 应用满足的条件和场景 本篇博客以《算法导论》第15章动态规划算法为本背景,大量引用书中内容和实例࿰…...

Jmeter添加cookie的两种方式
jmeter中添加cookie可以通过配置HTTP Cookie Manager,也可以通过HTTP Header Manager,因为cookie是放在头文件里发送的。 实例:博客园点击添加新随笔 https://i.cnblogs.com/EditPosts.aspx?opt1 如果未登录,跳转登录页…...

【ArcGIS Pro二次开发】(58):数据的本地化存储
在做村规工具的过程中,需要设置一些参数,比如说导图的DPI,需要导出的图名等等。 每次导图前都需要设置参数,虽然有默认值,但还是需要不时的修改。 在使用的过程中,可能会有一些常用的参数,希望…...
React配置代理服务器的5种方法
五种方法的介绍 以下是五种在React项目中配置代理服务器的方法的使用场景和优缺点: 1. 使用 http-proxy-middleware 中间件: 使用场景:适用于大多数React项目,简单易用。优点:配置简单,易于理解和维护。…...
树莓派:5.jar程序自启运行
搞了好长时间才搞定,普通的jar文件好启动。神奇的在于在ssh里启动GPIO可以操作,但是自启动GPIO不能控制。第二天才想明白估计是GPIO的操作权限比较高,一试果然如此,特此记录。 1、copy程序文件和sh文件在Public下 piraspberrypi…...
Vivado中SmartConnect和InterConnect的区别
前言:本文章为FPGA问答系列,我们会定期整理FPGA交流群(包括其他FPGA博主的群)里面有价值的问题,并汇总成文章,如果问题多的话就每周整理一期,如果问题少就每两周整理一期,一方面是希…...

了解HTTP代理日志:解读请求流量和响应信息
嗨,爬虫程序员们!你们是否在了解爬虫发送的请求流量和接收的响应信息上有过困扰?今天,我们一起来了解一下。 首先,我们需要理解HTTP代理日志的基本结构和内容。HTTP代理日志是对爬虫发送的请求和接收的响应进行记录的文…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...