【TypeScrpt算法】算法的复杂度分析

算法的复杂度分析

什么是算法复杂度?

不同的算法,其实效率是不一样的
让我举一个案例来比较两种不同的算法在查找数组中给定元素的时间复杂度
[1,2,3,4,5,6,7,...9999,n]

顺序查找

这种方法从头到尾遍历整个数组,依次比较每个元素和给定元素的值。
如果找到想等元素,则返回下标,如果遍历整个数组都找不到就返回-1。

function sequenSearch(array:number[],target:number) {
  let result = -1
  for (let i = 0;i<array.length;i++) {
    array[i] === target ? result = i : undefined
  }
  return result
}

最长时间复杂度:n
平均的时间复杂度: n / 2
image.png
该算法时间复杂度是O(n)

二分查找

这种算法假设数组是有序的,每次选择数组中间的元素与给定元素进行比较。
如果找到想等元素,则返回下,如果给定的元素比中间元素小,则在数组左半部分继续查找;如果给定的元素比中间元素大,则在数组右半部分继续查找。
这样每次查找都会将查找的范围减半,知道找到想等的元素或者查找范围为空。

function binarySearch(array: number[], target: number) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    const midTarget = array[mid];
    if (midTarget === target) {
      return mid;
    } else if (midTarget < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

最长时间复杂度:log(n,2)
平均的时间复杂度: log(n,2) / 2
image.png
该算法时间复杂度是O(log n)

大O表示法(Big O notation)

大O表示法(Big O notation)英文翻译为大O符号(维基百科翻译),中文通常翻译为大O表示法(标记法)。

  • 这个记号则是在德国数论学家爱德蒙·兰道的著作中才推广的,因此它有时又称为兰道符号(Landau symbols)。
  • 代表“order of …”.……阶)的大O,最初是一个大写希腊字母“O”(omicron),现今用的是大写拉丁字母“O”。

时间复杂度

分析算法时间效率举例

  • 举个例子,解决一个规模为n的问题所花费的时间(或者所需步骤的数目)可以表示为: T(n)=4n2-2n+2

  • n增大时,n2项开始占据主导地位,其他各项可以被忽略;

  • 举例说明:当n=500

  • 4n2项是2n项的1000倍大,因此在大多数场合下,省略后者对表达式的值的影响将是可以忽略不计的。
    进一步看,如果我们与任一其他级的表达式比较, n2的系数也是无关紧要的。
    这样,针对第一个例子T(n) = 4n2- 2n+2,大O符号就记下剩余的部分,写作:
    T(n) ∈ o(n2)

    T(n)= o(n2)
    我们就说该例子算法具有**n2**阶(平方阶)的时间复杂度,表示为**O(n2)**

常用函数阶

介绍

image.png

案例

image.png

图表

image.png

空间复杂度

空间复杂度指的是程序运行过程中所需要的额外存储空间。

空间复杂度也可以用大O表示法来表示;
空间复杂度的计算方法与时间复杂度类似,通常需要分析程序中需要额外分配的内存空间,如数组、变量、对象、递归调用等。

分析算法空间效率举例

举个栗子:
对于一个简单的递归算法来说,每次调用都会在内存中分配新的栈帧,这些栈帧占用了额外的空间。

  • 因此,该算法的空间复杂度是o(n),其中n是递归深度。
    而对于迭代算法来说,在每次迭代中不需要分配额外的空间,因此其空间复杂度为o(1)。
    当空间复杂度很大时,可能会导致内存不足,程序崩溃。
    在平时进行算法优化时,我们通常会进行如下的考虑:

  • 使用尽量少的空间(优化空间复杂度);

  • 使用尽量少的时间(优化时间复杂度);

  • 特定情况下:使用空间换时间或使用时间换空间;

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

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

相关文章

Jenkins+Maven+Gitlab+Tomcat 自动化构建打包、部署

JenkinsMavenGitlabTomcat 自动化构建打包、部署 1、环境需求 本帖针对的是Linux环境&#xff0c;Windows或其他系统也可借鉴。具体只讲述Jenkins配置以及整个流程的实现。 1.JDK&#xff08;或JRE&#xff09;及Java环境变量配置&#xff0c;我用的是JDK1.8.0_144&#xff0…

Talk | UCSB博士生宋珍巧:基于人工智能的功能性蛋白质设计

本期为TechBeat人工智能社区第549期线上Talk。 北京时间11月22日(周三)20:00&#xff0c;UC Santa Barbara博士生—宋珍巧的Talk已准时在TechBeat人工智能社区开播&#xff01; 她与大家分享的主题是: “基于人工智能的功能性蛋白质设计”&#xff0c;介绍了如何利用机器学习算…

好用的局域网监控软件推荐

局域网监控软件是一种用于监控局域网内计算机使用情况的软件&#xff0c;可以帮助企业管理者更好地了解员工的工作状态和行为&#xff0c;规范上网行为并保护企业网络资源。 一、域之盾软件 这是一款专业的上网监控软件&#xff0c;它支持多种操作系统和平台&#xff0c;可以全…

CodeWhisperer 体验总结

CodeWhisperer 体验总结 | CodeWhisperer 是一款亚马逊新推出的通用代码生成器 可以实时进行代码数据的提供 还可以定义安全问题 CodeWhisperer 对个人用户是免费使用 企业用户需要订阅使用 亚马逊云科技开发者社区为开发者们提供全球的开发技术资源。这里有技术文档、开发案例…

【精选】改进的YOLOv5:红外遥感图像微型目标的高效识别系统

1.研究背景与意义 随着科技的不断发展&#xff0c;红外遥感技术在军事、安防、环境监测等领域中得到了广泛应用。红外遥感图像具有独特的优势&#xff0c;可以在夜间或恶劣天气条件下获取目标信息&#xff0c;因此在小目标检测方面具有重要的应用价值。然而&#xff0c;由于红…

当当网获得dangdang商品详情商品列表API 测试请求入口

item_get-获得dangdang商品详情 获取商品详情 item_search-按关键字搜索dangdang商品 获取商品列表 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称&#xff08;包括在请…

python数据结构与算法-13_高级排序算法-快速排序

快速排序 快速排序名字可不是盖的&#xff0c;很多程序语言标准库实现的内置排序都有它的身影&#xff0c;我们就直奔主题吧。 和归并排序一样&#xff0c;快排也是一种分而治之(divide and conquer)的策略。归并排序把数组递归成只有单个元素的数组&#xff0c;之后再不断两两…

PC端页面进去先出现加载效果

自定义指令v-loading&#xff0c;只需要绑定Boolean即可 v-loading“loading” <el-table :data"list" border style"width: 100%" v-loading"loading"><el-table-column align"center" label"序号" width"5…

java--static修饰成员变量

1.static 叫静态&#xff0c;可以修饰成员变量、成员方法。 2.成员变量按照有无static修饰&#xff0c;分为两种&#xff1a; ①类变量&#xff1a;有static修饰&#xff0c;属于类&#xff0c;在计算机里只有一份&#xff0c;会被类的全部对象共享(不管那个类调用的&#x…

脸爱云一脸通智慧管理平台未授权访问

声明 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 一、漏洞概述 脸爱云一脸通智慧管理平台存在严重漏洞&#xff0c;允许…

数据结构与算法编程题13

设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C&#xff0c;其中B表的结点为A表中值小于零的结点&#xff0c;而C表的结点为A表中值大于零的结点&#xff08;链表A中的元素为非零整数&#xff0c;要求B、C表利用A表的结点&#xff09; for example: A -1 2 …

企业软件定制开发有哪些优势?|app小程序网站搭建

企业软件定制开发有哪些优势&#xff1f;|app小程序网站搭建 企业软件定制开发是一种根据企业特定需求开发定制化软件的服务。相比于购买现成的软件产品&#xff0c;企业软件定制开发具有许多优势。 首先&#xff0c;企业软件定制开发可以满足企业独特需求。每个企业都有自己独…

C++基础从0到1入门编程(四)类和对象

系统学习C 方便自己日后复习&#xff0c;错误的地方希望积极指正 往期文章&#xff1a; C基础从0到1入门编程&#xff08;一&#xff09; C基础从0到1入门编程&#xff08;二&#xff09; C基础从0到1入门编程&#xff08;三&#xff09; 参考视频&#xff1a; 1.黑马程序员匠心…

OpenGL YUV 和 RGB 图像相互转换出现的偏色问题怎么解决?

未经作者(微信ID:Byte-Flow)允许,禁止转载 文章首发于公众号:字节流动 早上知识星球里的一位同学,遇到 yuv2rgb 偏色问题,这个问题比较典型,今天展开说一下。 省流版 首先 yuv2rgb 和 rgb2yuv 之间的转换要基于相同的标准,转换使用不同的标准肯定会引起偏色,常见的…

Leetcode1410. HTML 实体解析器

Every day a Leetcode 题目来源&#xff1a;1410. HTML 实体解析器 解法1&#xff1a;模拟 遍历字符串 text&#xff0c;每次遇到 ’&‘&#xff0c;就判断以下情况&#xff1a; 双引号&#xff1a;字符实体为 &quot; &#xff0c;对应的字符是 " 。单引号&a…

技术短视频账号矩阵seo系统--源头开发---saas工具

专注短视频账号矩阵系统源头开发---saas营销化工具&#xff0c;目前我们作为一家纯技术开发团队目前已经专注打磨开发这套系统企业版/线下版两个版本的saas营销拓客工具已经3年了&#xff0c;本套系统逻辑主要是从ai智能批量剪辑、账号矩阵全托管发布、私信触单收录、文案ai智能…

el-table表格排序(需要后端判别),el-table导出功能(向后端发送请求)

&#xff08;1&#xff09;表格排序 &#xff08;2&#xff09;简单的table导出功能&#xff08;需要后台支撑&#xff09;必须要有iframe &#xff08;3&#xff09;页面所有代码&#xff1a; <template><div class"mainContainer"><el-form:model&…

护眼台灯怎么样选择?口碑最好的五款护眼台灯推荐

7月13日&#xff0c;国家卫生健康委疾控局公布了一项覆盖了全国8604所学校&#xff0c;247.7万名学生的近视专项调查结果。结果显示&#xff0c;2020年&#xff0c;我国儿童青少年总体近视率为52.7%&#xff1b;其中6岁儿童为14.3%&#xff0c;小学生为35.6%&#xff0c;初中生…

Find My按摩仪|苹果Find My技术与按摩仪结合,智能防丢,全球定位

工作生活中&#xff0c;颈椎总会经常不舒服&#xff0c;尤其像我们这种低头族&#xff0c;上班用电脑&#xff0c;下班玩手机&#xff0c;每天的颈椎保持一个状态而得不到休息&#xff0c;从而让我们的颈椎不舒服&#xff0c;患上了颈椎病。颈椎僵硬&#xff0c;肌肉紧张&#…