美文网首页
10大经典算法

10大经典算法

作者: 张德瘦嬢嬢 | 来源:发表于2020-12-29 16:35 被阅读0次

参考阅读

算法的时间和空间复杂度

什么是算法

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源(空间复杂度)和时间(时间复杂度)却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢?

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

  • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
  • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点

下面我来分别介绍一下「时间复杂度」和「空间复杂度」的计算方式。

反映的是一个趋势****反映的是一个趋势****反映的是一个趋势****反映的是一个趋势****反映的是一个趋势****反映的是一个趋势

时间复杂度不是用来计算程序具体耗时的,那么我也应该明白,空间复杂度也不是用来计算程序实际占用的空间的。

image.png

1.快速排序

快速排序由于排序效率在同为O(NlogN)*的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用

2. 冒泡排序

算法思想

  • 基本思想: 冒泡排序,类似于水中冒泡,较大的数沉下去,较小的数慢慢冒起来,假设从小到大,即为较大的数慢慢往后排,较小的数慢慢往前排。
  • 直观表达,每一趟遍历,将一个最大的数移到序列末尾。

算法描述

  • 比较相邻的元素,如果前一个比后一个大,交换之。
  • 第一趟排序第1个和第2个一对,比较与交换,随后第2个和第3个一对比较交换,这样直到倒数第2个和最后1个,将最大的数移动到最后一位。
  • 接下来第二趟,忽略已经拍好的数字,对于剩下的数字再来一轮
    ......
    动画实现
image

第一轮:

  1. 选择 10 和 34, 进行比较, 其中 10 < 34, 二者不需要交换
  2. 选择 34 和 21, 进行比较, 其中 34 > 21, 二者需要交换
  3. 选择 34 和 47, 进行比较, 其中 34 < 47, 二者需不要交换
  4. 选择 47 和 3, 进行比较, 其中 47 > 3, 二者需要交换
  5. ...
  6. 最后 47 交换到末尾

第二轮:

忽略已经排列好的47, 按照刚刚的逻辑再次排序

...

[图片上传失败...(image-e38d47-1609230829454)]

复杂度

let arr = randomArr(10000, 100)
console.time('bubleSort')  //开始时间
bubleSort(arr)
console.timeEnd('bubleSort')  //结束时间


function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}

function bubleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length - i; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
      }
    }
  }
}
1w长度数组发现平均时间: image.png

以下是10-10万数组长度排序所花时间

image.png

发时间复杂度: [图片上传失败...(image-c3282c-1609230829454)]

空间复杂度: [图片上传失败...(image-39bce5-1609230829454)]

稳定性:稳定

代码实现(JavaScript)

image.png

function bubleSort(arr) {
  for(let i = 0; i < arr.length /*i代表轮数*/; i++) {
    for(let j = 0; j < arr.length - i /*j代表当前轮选中的元素下标*/; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
      }
      //console.log(arr)
    }
  }
}

var arr = [10, 34, 21, 47, 3, 28]
bubleSort(arr)
console.log(arr)

3. 插入排序

代码实现(JavaScript)

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    for(let j = 0; j < i; j++) {
      if(arr[i] < arr[j]) {
        arr.splice(j, 0, arr[i])
        arr.splice(i+1, 1)
        break
      }
      console.log(arr)
    }
  }
}

var arr = [10, 34, 21, 47, 3, 28]
insertionSort(arr)
console.log(arr)

复杂度

时间复杂度为 O(n^2) ,和上面的测试基本一致。

相关文章

  • 常见算法

    一、【经典算法大全】收集51种经典算法 初学者必备

  • 12月,献上的12本Java架构师必读书籍

    经典算法谜题的合集Google、Facebook等一流IT公司算法面试必备 《算法谜题》是经典算法谜题的集结。它列...

  • 算法学习记录

    可视化算法 白话经典算法

  • 学习路线规划

    目前有两本书,《算法竞赛入门经典》和《算法竞赛进阶指南》。根据书名应该先看《算法竞赛入门经典》( 《算法竞赛入门经...

  • 序言-算法

    此文集将介绍一些经典的算法,从经典的排序算法开始不定期的补充纠错更新 1、经典排序算法 1.1桶排序Bucket ...

  • 《算法竞赛入门经典(第2版) 算法艺术与信息学竞赛》PDF高清完

    《算法竞赛入门经典(第2版) 算法艺术与信息学竞赛》PDF高清完整版-免费下载 《算法竞赛入门经典(第2版) 算法...

  • Clustering

    本文结构安排 经典聚类算法:线性聚类 Kmeans 经典聚类算法:非线性聚类 DBSCAN、谱聚类 新兴聚类算法:...

  • python3同态加密算法实现

    目前同态加密算法分为加法同态和乘法同态,而加法同态中最经典的是paillier算法,乘法同态中最经典的是rsa算法...

  • 十大经典排序算法&七大查找算法

    十大经典排序算法: 十大经典排序算法的时间、空间复杂度: 冒泡排序(Bubble Sort) 算法描述: 1、比较...

  • Clustering

    Clustering 算法概念 算法类型 K-means算法是非监督学习聚类(clustering)中的经典算法,...

网友评论

      本文标题:10大经典算法

      本文链接:https://www.haomeiwen.com/subject/fixqoktx.html