【数据结构与算法——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代理日志是对爬虫发送的请求和接收的响应进行记录的文…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...