前端常用的几种算法的特征、复杂度、分类及用法示例演示

算法（Algorithm）可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法代表着用系统的方法描述解决问题的策略机制，它能够对一定规范的输入在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法分类

  • 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

  • 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

在这里插入图片描述

算法特征
  • 有穷性(Finiteness)：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
  • 确切性(Definiteness)：算法的每一步骤必须有确切的定义；
  • 输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
  • 输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
  • 可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。
算法复杂度

在这里插入图片描述

  • 时间复杂度
    算法的时间复杂度是指执行算法所需要的计算工作量。因此，问题的规模越大，算法执行的时间的增长率与的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

  • 空间复杂度
    算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

1. 冒泡排序

这是一种简单的排序算法，通过重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  for(let i = 0;i<arr.length-1;i++){
    for(let j = 0;j<arr.length-1-i;j++){
      if(arr[j]>arr[j+1]){
        let temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp
      }
    }
  }
  return arr
}
sort(arr)
console.log(arr);

算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。
2. 插入排序

这是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  for(var i =1;i<arr.length;i++){
    var val = arr[i];
    var last = i-1;
    while(last>=0 && arr[last]>val){
      arr[last+1] = arr[last]
      last--
    }
    arr[last+1] = val
  }
  return arr
}
sort(arr)
console.log(arr);

算法描述

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5。
3. 快速排序

快速排序使用分治的原理，它选择一个元素作为"基准"，然后将所有其他元素分成两组，第一组包括所有小于基准的元素，第二组包括所有大于或等于基准的元素。然后对这两组进行递归排序。这就是分治策略的基本步骤。

var arr = [1,56,9,6,3,5,8,2]
function quickSort(arr){
  if(arr.length<2){
    return arr
  }
  var mid = Math.floor(arr.length/2)
  var pivot = arr.splice(mid,1)[0]
  var left = [];
  var right = [];
  for(var i = 0;i<arr.length;i++){
    if(arr[i]<pivot){
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat(pivot,quickSort(right))
}
console.log(quickSort(arr));

算法描述

  1. 从数列中挑出一个元素，称为 “基准”（pivot）；
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4. 归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

var arr = [1,56,9,6,3,5,8,2];
function mergeSort(arr) {
  var len = arr.length
  if(len<2){
    return arr
  }
  var mid = Math.floor(arr.length/2)
  var left = arr.slice(0,mid)
  var right = arr.slice(mid)
  return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right) {
  var result = []
  while(left.length>0 && right.length>0){
    if(left[0]>right[0]){
      result.push(right.shift())
    } else {
      result.push(left.shift())
    }
  }
  while(left.length){
    result.push(left.shift())
  }
  while(right.length){
    result.push(right.shift())
  }
  arr = result
  return arr
}
mergeSort(arr)
console.log(arr);

算法描述

  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。
5. 希尔排序

希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  var gap = arr.length
  for(gap = Math.floor(arr.length/2);gap>0;gap = Math.floor(gap/2)){
    for(var i=gap;i<arr.length;i++){
      var val = arr[i];
      var  j = i;
      while(j-gap>=0 && arr[j-gap]>val){
        arr[j] = arr[j-gap]
        j = j-gap
      }
      arr[j] = val
    }
  }
  return arr
}
sort(arr)
console.log(arr);

算法描述

  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列个数k，对序列进行k 趟排序；
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
6. 堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,…,hn)，当且仅当满足（hi<=h2i,hi<=h2i+1）或（hi>=h2i,hi>=h2i+1） (i=1,2,…,n/2)时称之为堆。在这里只讨论满足hi>=h2i,hi>=h2i+1，且hj>=hk（j>k）的堆称为对于堆排序来说，最重要的一步是将待排序的序列构造成一个大顶堆（或小顶堆）。

var arr = [1,56,9,6,3,5,8,2]
var len; 
function buildMaxHeap(arr) {
  len = arr.length
  for(var i = 0;i<Math.floor(arr.length/2);i++){
    heapify(arr,i)
  }
}
function heapify(arr,i){
  var left = i*2+1;
  var right = i*2+2;
  var largest = i;
  if(left<len && arr[left]>arr[largest]){
    largest = left
  }
  if(right<len && arr[right]>arr[largest]){
    largest = right
  }
  if(largest !== i){
    swap(arr,i,largest)
    heapify(arr,largest)
  }
}
function swap(arr,i,j){
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp
}
function heapSort(arr){
  buildMaxHeap(arr) 
  for(var i = arr.length-1;i>=0;i--){
    len-=1;
    swap(arr,0,i)
    heapify(arr,0)
  }
  return arr
}
console.log(heapSort(arr));

算法描述

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
7. 计数排序

计数排序是一种非比较型的排序算法，适合于对一定范围内的整数排序。它的基本思想是通过为每个整数x计算其出现的次数，得到一个频率表，然后依次输出每个整数x出现的次数，实现排序。

var arr = [1,56,9,6,3,5,8,2];
function countingSort(arr, maxValue){
  var bucket = new Array(maxValue+1)
  var index = 0
  for(var i =0;i<arr.length;i++){
    if(!bucket[arr[i]]){
      bucket[arr[i]] = 0
    }
    bucket[arr[i]]++
  }
  for(var j = 0;j<bucket.length;j++){
    while(bucket[j]>0){
      arr[index++] = j
      bucket[j]--
    }
  }
  return arr
}
console.log(countingSort(arr,56));

算法描述

  1. 找出待排序的数组中最大和最小的元素；
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
  4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
8. 选择排序

这是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

var arr = [1,56,9,6,3,5,8,2]
function sort(arr){
  for(let i =0;i<arr.length-1;i++){
    var index
    let min = i
    for(let j = i+1;j<arr.length;j++){
      if(arr[j]<arr[min]){
        min = j
      }
    }
      var temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp
  }
  return arr
}
sort(arr)
console.log(arr);

算法描述

  1. 初始状态：无序区为R[1…n]，有序区为空；
  2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  3. n-1趟结束，数组有序化了。

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

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

相关文章

两整数之和 -- 位运算

两整数之和 -- 位运算

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 本题链接 力扣&#xff08;LeetCode&#xff09; 输入描述 输入两个要相加的数&#xff0c;a和b 输出描述 返回a和b的和&#xff0c;这里其实直接return ab; 直接就过了&#xff0c;但是人题目要求还是给点面子~ 算法…
阅读更多...
mariadb实现主从同步

mariadb实现主从同步

准备两台服务器 Mariadb-Master&#xff1a;192.168.44.150 Mariadb-Backup&#xff1a;192.168.44.148 安装mariadb&#xff1a; https://blog.csdn.net/qq_50247813/article/details/135402502?spm1001.2014.3001.5502 组从复制原理如下 修改主数据库配置如下 vi /etc/my.…
阅读更多...
钼铁，需求量将推动市场进入新一轮发展浪潮

钼铁，需求量将推动市场进入新一轮发展浪潮

钼铁是一种重要的冶金原料&#xff0c;广泛用于制造高速钢、不锈钢、合金钢、特殊钢等钢材&#xff0c;并且被广泛应用于核工业、电子工业、航空航天等高技术产业领域。随着钢铁市场的不断发展&#xff0c;钼铁市场也逐渐壮大&#xff0c;下面将从全球市场和中国市场分析其发展…
阅读更多...
自学 c++ 要掌握哪些技巧和方法？

自学 c++ 要掌握哪些技巧和方法？

自学 c 要掌握哪些技巧和方法&#xff1f; 在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「C的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&…
阅读更多...
大模型在现代应用中的多元实例

大模型在现代应用中的多元实例

目录 前言1 GPT-3、GPT-3.5、GPT-4&#xff1a;自然语言处理的新纪元1.1 GPT-3与传统NLP方法的区别1.2 GPT-3.5 和 GPT-4 的进展1.3 技术背后的革新 2 自然语言转换为Python代码2.1 简介2.2 技术原理2.3 应用和优势 3 DALL-E 2&#xff08;5B&#xff09;图像生成3.1 简介3.2 技…
阅读更多...
LauraGPT

LauraGPT

git&#xff1a;https://github.com/alibaba-damo-academy/FunCodec 文章目录 model archAudioTokenizermodel init model arch text-embedding 用千问的模型参数初始化&#xff1b;AudioEncoder用asr-conformer的参数初始化&#xff1b;所有的参数都参与更新&#xff0c;除了C…
阅读更多...
【动态规划】C++算法：115.不同的子序列

【动态规划】C++算法：115.不同的子序列

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 LeetCode115 不同的子序列 给你两个字符串 s 和 t &#xff0c;统计并返回在 s 的 子序列 中 t 出现的个数&#xff0c;结果需要对 109 7 取模。 示例 1&#xff1a; 输入&#xff1a;s “rab…
阅读更多...
如何让CHAT使用python绘制概率密度图像？

如何让CHAT使用python绘制概率密度图像？

问CHAT&#xff1a;用python绘制概率密度图像 CHAT回复&#xff1a;你可以使用Python的matplotlib库和numpy库进行概率密度的绘制。 以下是一个简单的例子&#xff1a; python import numpy as np import matplotlib.pyplot as plt #随机生成1000个正态分布的数 data np.rand…
阅读更多...
无法开机报 不可恢复的错误：securityagent无法创建所要求的机制Teamviewerauthplugin:start

无法开机报 不可恢复的错误：securityagent无法创建所要求的机制Teamviewerauthplugin:start

无法开机报 不可恢复的错误&#xff1a;securityagent无法创建所要求的机制Teamviewerauthplugin:start 初步判断很有可能是TeamViewer的某个启动项或者签名书没有&#xff0c; 导致在预加载的时候无法加载TeamViewer。 然后出现这个情况有一个前提&#xff0c;那就是你用了第三…
阅读更多...
Linux_CentOS_7.9配置时区及NTPdate同步之简易记录

Linux_CentOS_7.9配置时区及NTPdate同步之简易记录

前言&#xff1a;ntpdate命令来自英文词组”NTPdate“的拼写&#xff0c;其功能是用于设置日期和时间。ntpdate命令能够基于NTP协议设置Linux系统的本地日期和时间&#xff0c;利用NTP服务的时钟过滤器来选择最优方案&#xff0c;大大提高了可靠性和精度&#xff0c;让系统时间…
阅读更多...
【RabbitMQ】1 消息中间件MQ概述

【RabbitMQ】1 消息中间件MQ概述

目录 什么是消息中间件为什么使用消息中间件流量削峰应用解耦异步处理 主流消息中间件及选型选取原则RabbitMQRocketMQKafka如何选择 消息中间件应用场景电商秒杀案例拉勾B端C端数据同步案例支付宝购买电影票 什么是消息中间件 维基百科对消息中间件的解释&#xff1a;面向消息…
阅读更多...
宽压输入1.5KV隔离直流高压输出电源模块

宽压输入1.5KV隔离直流高压输出电源模块

GRC系列低成本小体积宽电压输入隔离高压模块电源&#xff0c;是一款业界的隔离稳压型DC-DC高电压转换器&#xff0c;可在宽范围波动的不稳定电压输入环境中运行&#xff0c;通过模块的内部调整电路可以生成隔离稳压的直流高电压输出。产品外壳采用铝壳喷塑防腐设计&#xff0c;…
阅读更多...
栈的数据结构实验报告

栈的数据结构实验报告

一、实验目的&#xff1a; 1、理解栈的定义&#xff1b; 2、利用栈处理实际问题。 二、实验内容&#xff08;实验题目与说明&#xff09; 利用栈实现数据的分类&#xff0c;将输入的整数以奇偶为标准分别存放到两个栈中&#xff0c;并最终从栈1和栈2输出偶数和奇数序列。 …
阅读更多...
如何培养学生的创造性思维

如何培养学生的创造性思维

在当下这个时代&#xff0c;创造力的重要性不言而喻。如何在日常教育中潜移默化地培养孩子的创造性思维呢&#xff1f; 一、激发好奇心&#xff0c;让思维自由飞翔 孩子天生就有一颗好奇的心&#xff0c;作为老师&#xff0c;要鼓励他们提问&#xff0c;鼓励他们去探索。好奇…
阅读更多...
风车模型与代码

风车模型与代码

这个模型使用NetLogo乌龟来重复绘制圆圈&#xff0c;定期转动&#xff0c;以便显示出类似万花筒或风车的效果。这是一个演示&#xff0c;展示了一组简单的代理规则如何产生复杂而美丽的图案。 内部工作原理非常简单。创建了许多乌龟&#xff0c;它们的笔都是放下的&#xff08…
阅读更多...
电子化学品，预计2025年会增长到4302亿美元

电子化学品，预计2025年会增长到4302亿美元

电子化学品市场是一个庞大的细分市场&#xff0c;它包括了广泛的化学品种类&#xff0c;如涂料、塑料、精细化学品、农药和医药等。这个市场的发展相当迅速&#xff0c;下面我们将从全球市场和中国市场两个方面对其发展趋势进行分析。全球市场分析&#xff1a; 从全球市场的角度…
阅读更多...
【HBase】——优化

【HBase】——优化

1 RowKey设计 重要&#xff1a;一条数据的唯一标识就是 rowkey&#xff0c;那么这条数据存储于哪个分区&#xff0c;取决于 rowkey 处于 哪个一个预分区的区间内&#xff0c;设计 rowkey的主要目的 &#xff0c;就是让数据均匀的分布于所有的 region 中&#xff0c;在一定程度…
阅读更多...
Java重修第二天—学习”方法“

Java重修第二天—学习”方法“

通过学习本篇文章可以掌握如下知识 1、方法的定义 2、方法在计算机中的执行流程。 3、方法使用时常见问题 4、Java中方法的参数传递机制 5、方法重载 1 方法是什么 方法是一种语法结构&#xff0c;它可以把一段代码实现的某种功能封装起来&#xff0c;以便重复利用。 方…
阅读更多...
杰发科技AC7801——IO模拟IIC注意事项

杰发科技AC7801——IO模拟IIC注意事项

7801的参考手册没有说清楚 7840说明了用开漏 使用办法
阅读更多...
Java 支持表情包存储 Incorrect string value: ‘\\xF0\\x9F\\x98\\x8A\\xF0\\x9F...‘

Java 支持表情包存储 Incorrect string value: ‘\\xF0\\x9F\\x98\\x8A\\xF0\\x9F...‘

一&#xff0c;前言 最近测试提出了一个比较刁钻的bug 在提交表单数据的时候&#xff0c;支持表情输入&#xff0c;如下 看了一下前端参数&#xff0c;也是正常传递 但是调用接口的时候&#xff0c;后端却报错 Cause: java.sql.SQLException: Incorrect string value: \\xF0…
阅读更多...
最新文章

Copyright @ 2022~2023