【数据结构与算法——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)

  • ❣️ 我们就说该算法 具有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 StructureAccessSearchInsertionDeletion
ArrayO(1)O(N)O(N)O(N)
Linked ListO(N)O(N)O(1)O(1)
  • 数组是一种连续的存储结构,通过下标可以直接访问数组中的任意元素

    • 时间复杂度: 对于数组,随机访问时间复杂度为O(1),插入和删除操作的时间复杂度为O(n)。
    • 空间复杂度:数组需要连续的存储空间,空间复杂度为 O(n)
  • 链表,是一种链式存储结构,通过指针链接起来的节点组成,访问链表中元素需要从头结点开始遍历

    • **时间复杂度:**对于链表,随机访问时间复杂度为O(n),插入和删除的时间复杂度为O(1)
    • **空间复杂度:**链表需要为每个节点分配存储空间,空间复杂度为O(n)
  • 💖 在实际开发中,选择使用数组还是链表需要根据具体应用场景来决定

    • 如果数据量不大,且需要频繁随机访问元素,使用数组可能会更好
    • 如果数据量很大,或者需要频繁插入和删除元素,使用链表可能会更好

【数据结构与算法——TypeScript】系列笔记:
1. 【数据结构与算法——TypeScript】数组、栈、队列、链表

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/59721.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【百问百答】可靠性基础知识第七期

1.什么是振动频率范围? 振动频率范围表示振动试验由某个频率点到另一个频率点进行往复扫频。 例如&#xff1a;试验频率范围5~500Hz&#xff0c;表示5Hz到500Hz进行往复扫频 2.什么是振动量? 振动量&#xff1a;通常用加速度和位移来表示&#xff1b; 加速度&#xff1a;表…

react学习笔记——1. hello react

包含的包一共有4个&#xff0c;分别的作用如下&#xff1a; babel.min.js&#xff1a;可以进行ES6到ES5的语法转换&#xff1b;可以用于import&#xff1b;可以用于将jsx转换为js。注意&#xff0c;在开发的时候&#xff0c;这个转换&#xff08;jsx转换js&#xff09;不在线上…

webshell详解

Webshell详解 一、 Webshell 介绍二 、 基础常见webshell案例 一、 Webshell 介绍 概念 webshell就是以asp、php、jsp或者cgi等网页文件形式存在的一种命令执行环境&#xff0c;也可以将其称做为一种网页后门。黑客在入侵了一个网站后&#xff0c;通常会将asp或php后门文件与…

vscode如何退出/切换 github 账号

退出/切换 github 账号 左下角点击头像按钮&#xff0c;选择注销&#xff0c;然后再重新登录

计算机视觉:替换万物Inpaint Anything

目录 1 Inpaint Anything介绍 1.1 为什么我们需要Inpaint Anything 1.2 Inpaint Anything工作原理 1.3 Inpaint Anything的功能是什么 1.4 Segment Anything模型&#xff08;SAM&#xff09; 1.5 Inpaint Anything 1.5.1 移除任何物体 1.5.2 填充任意内容 1.5.3 替换任…

react ant add/change created_at

1.引入ant的 Table import { Table, Space, Button, message } from antd; 2.获得接口的数据的时候增加上创建时间 const response await axios.get(${Config.BASE_URL}/api/v1/calculation_plans?token${getToken()});if (response.data.message ok) {const data respon…

Scrum是什么意思,Scrum敏捷项目管理工具有哪些?

一、什么是Scrum&#xff1f; Scrum是一种敏捷项目管理方法&#xff0c;旨在帮助团队高效地开展软件开发和项目管理工作。 Scrum强调迭代和增量开发&#xff0c;通过将项目分解为多个短期的开发周期&#xff08;称为Sprint&#xff09;&#xff0c;团队可以更好地应对需求变…

2023华数杯数学建模C题完整5问代码思路分析

目前已经写出2023华数杯C题母亲身心健康对婴儿成长的影响全部5问的完整代码和42页论文&#xff08;正文30页&#xff0c;论文部分摘要如下&#xff1a; 本文共解决了五个问题&#xff0c;涉及婴儿行为特征、睡眠质量与母亲的身体指标和心理指标的关系&#xff0c;以及如何优化…

STL C++学习背景

STL C学习背景 背景知识 背景知识 STL前置知识 STL&#xff0c;英文全称 standard template library&#xff0c;中文可译为标准模板库或者泛型库&#xff0c;其包含有大量的模板类和模板函数&#xff0c;是 C 提供的一个基础模板的集合&#xff0c;用于完成诸如输入/输出、数…

【Linux】Linux工具

Yan-英杰的主页 悟已往之不谏 知来者之可追 C程序员&#xff0c;2024届电子信息研究生 目录 一、Linux安装软件&#xff1a; 1.yum安装 2.Linux和Windows文件互传 问题: 3.yum卸载软件 二、vim编辑器 1.命令模式 2.vim配置项说明 3.vim操作总结 一、Linux安装软件&#…

DC-4靶机

信息收集 先查看靶机的MAC地址 arp-scan -l 找到目标靶机的IP地址&#xff0c;对其进行扫描 发现开放了80端口和ssh&#xff0c;浏览器访问靶机的80端口&#xff0c;看看有没有可以利用的东西 目录爆破发现也没有什么东西 dirsearch -u http://192.168.80.146 漏洞利用 利用…

LUN映射出错导致写操作不互斥的服务器数据恢复案例

服务器数据恢复环境&#xff1a; 某公司的光纤SAN存储系统&#xff0c;6块硬盘组建一组RAID6&#xff0c;划分若干LUN&#xff0c;MAP到不同的SOLARIS操作系统服务器上。 服务器故障&分析&#xff1a; 由于业务增长需要新增应用&#xff0c;工作人员增加了一台IBM服务器&am…

16-1_Qt 5.9 C++开发指南_多语言界面

文章目录 1. 多语言界面设计概述2. tr()函数的使用3. 生成语言翻译文件4. 使用Qt Linguist 翻译 ts 文件5. 调用翻译文件改变界面语言5.1 生成qm文件5.2 项目启动时设置界面语言5.3 动态切换语言 1. 多语言界面设计概述 有些软件需要开发多语言界面版本&#xff0c;如中文版和…

Cesium 工程模板

1、vue2.x cli https://github.com/948033145/anov-gis-vue2 2、vue3.x vite https://github.com/948033145/anov-gis-vite 下载代码 anov-gis-vue2.x.zip 下载代码 anov-gis-vite.zip

云原生应用里的服务发现

服务定义&#xff1a; 服务定义是声明给定服务如何被消费者/客户端使用的方式。在建立服务之间的同步通信通道之前&#xff0c;它会与消费者共享。 同步通信中的服务定义&#xff1a; 微服务可以将其服务定义发布到服务注册表&#xff08;或由微服务所有者手动发布&#xff09;…

剑指 Offer !!56 - II. 数组中数字出现的次数 II

剑指 Offer 56 - II. 数组中数字出现的次数 II 在一个数组 nums 中除一个数字只出现一次之外&#xff0c;其他数字都出现了三次。请找出那个只出现一次的数字。示例 1&#xff1a;输入&#xff1a;nums [3,4,3,3] 输出&#xff1a;4 示例 2&#xff1a;输入&#xff1a;nums …

Rpc原理

dubbo原理 1、RPC原理 一次完整的RPC调用流程&#xff08;同步调用&#xff0c;异步另说&#xff09;如下&#xff1a; 1&#xff09;服务消费方&#xff08;client&#xff09;调用以本地调用方式调用服务&#xff1b; 2&#xff09;client stub接收到调用后负责将方法、参数…

解密SpringMVC:探秘常用注解,让你的Java应用飞速起航!

这里写目录标题 什么是 Spring MVC&#xff1f;常用注解RequestMappingRequestParamRequestBodyPathVariableRequestPart 什么是 Spring MVC&#xff1f; Spring MVC是Spring框架中的一个模块&#xff0c;是基于Java的Web应用程序开发框架。它提供了一种用于构建灵活、高效、可…

数学建模-爬虫系统学习

尚硅谷Python爬虫教程小白零基础速通&#xff08;含python基础爬虫案例&#xff09; 内容包括&#xff1a;Python基础、Urllib、解析&#xff08;xpath、jsonpath、beautiful&#xff09;、requests、selenium、Scrapy框架 python基础 进阶&#xff08;字符串 列表 元组 字典…

如何使用ONLYOFFICE+ffmpeg来给视频文件打马赛克

如何使用ONLYOFFICEffmpeg来给视频文件打马赛克 我这里之前写过很多关于ONLYOFFICE使用、安装的系列图文&#xff0c;也写过很多关于ffmpeg使用的图文&#xff0c;那么这次继续&#xff0c;把这两个开源软件放在一起&#xff0c;能碰撞出什么火花般的功能来。 这就是给视频文…