时间复杂度与空间复杂度


时间复杂度：算法中重复执行的次数作为算法时间复杂度。

常见的时间复杂度
（1）O(1):常数复杂度
最常见的哈希表就是 O(1)，哈希表是通过哈希函数映射，类似于 y=hash(x),通过 hash 函数能迅速找到表中的值（暂时不考虑由于两个 x 值通过 hash 算法算出来 y 值相等的情况,如果有相应也有相应的解决方案），和数据没有关系，所以每次操作都是恒定时间。Chrome 里面对象属性的查找，在某些条件下就是用的哈希映射来查找属性。
（2）O(n):线性复杂度
随着数据的增加，复杂度也随之增加，例如从一堆数字中找到最小的数字，那么每一个都要循环到，复杂度就是线性复杂度。
（3）O(log n):对数复杂度
这种复杂度，代表案例就是二分法查找，假设有一串已经排序好从小到大的数字，查找其中是否有 X，那么从中间开始查找，中间数字大于 X，证明 X 应该在中间数字左边，所以舍去右边一半数字，再进行中间值查找比较，以此循环操作。
比如有 32 个数字，那么丢掉 16，下一轮是 16，再丢掉 8 个，每次丢一半，log(32)=5,这个 log 是以 2 为底，如果有 N 个，那么重复次数就是 log(N),也就是需要 log(N)次才能找到数字。在算法中，常数往往忽略，所以以二为底，以三为底都最后统一写成 log(N)形式。
里面有个相似复杂度 O(nlogn) ,数组快排排序，随便找一个数字，数组其他数字跟它比较，小于的放左边，大于的放右边，每一个都要比较，所以是 n 次，那么分成两块又可以放入二分法中思考，每次把数字一分为二，什么时候只剩一下一个数字就结束，那么二分法的复杂度是 log(n),那么合起来就是 N*log(n)的复杂度
下边是常见的两种代码形式

  1. O(logN)代码形式：
  2. int i = 1;
  3. while(i<n)
  4. {
  5.     i = i * 2;
  6. }
  8. O(NlogN)代码形式，时间复杂度为O(logN)的代码循环N遍
  9. for(m=1; m<n; m++)
  10. {
  11.     i = 1;
  12.     while(i<n)
  13.     {
  14.         i = i * 2;
  15.     }
  16. }

（4）O(n²):平方复杂度
最简单的理解，有两层循环时候，就会有 n² 复杂度，当有两个数组 i，j，在循环 i 数组内同时循环数组 j，那么复杂度就是 n²

空间复杂度
运行程序所需要的内存大小，所以关于这方面的思考常常需要会算你处理的数据大体大小是多少。比如 10 亿 int 整型数能否放到内存 1G 机器中计算？一个 int 类型是四个字节，那么 10 亿个四字节，就是四十亿字节，4000000000(字节)约等于 4GB，那么 1G 内存一次是放不下这么大数字的。

稳定性

如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前

交换数组中的两个元素位置

第一种方式
let tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;

第二种方式
[arr[i],arr[j]] = [arr[j],arr[i]]

排序算法

https://www.jianshu.com/p/1b4068ccd505

image.png

冒泡排序

image.png
image.png

const arr= [22,3,4,42,23,1,21,3,432,32];

function BubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    //共扫描的趟数
    for (let j = 0; j < len - 1 - i; j++) {
      //每趟扫描的个数
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}
console.log(BubbleSort(arr))

数组中第K大的数

var findKthLargest = function (nums, k) {
  for (let i = 0; i < k; i++) {
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1])
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
    }
  }
  return nums[nums.length - k]
};

选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度 O(n²) [数据规模越小越好] 不占用额外空间

image.png

function selectSort(arr) {
  let tmp, minIndex;
  for (let i = 0; i < arr.length; i++) {
    minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      //j从i的后面开始
      if (arr[j] < arr[minIndex]) {
        minIndex = j; //找到最小值的索引
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

console.log('select sort ',selectSort(arr))

插入排序

**工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
image.png

function insertSort(arr){
  let len = arr.length;
  for(let i=1; i<len;i++){ //i从1开始
    let tmp = arr[i];
    let j = i-1; //j从i的前面位置开始向前
    while(j>=0 && arr[j]>tmp){
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = tmp;
  }
  return arr
}

快速排序

快速排序就是个二叉树的前序遍历
image.png
image.png

function qSort(arr) {
  if (arr.length === 0) return [];
  var left = [],right = [];
  var pivotIndex = Math.floor(arr.length / 2); 
  var privot = arr.splice(pivotIndex, 1)[0];  //spilce返回的是数组
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < privot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return qSort(left).concat(privot, qSort(right));
}

归并排序

归并排序就是个二叉树的后序遍历
image.png
image.png

function mergeSort(array){  
  if (array.length === 1) return array;  
  var middle = Math.floor(array.length / 2);  //求出中点  
  var left = array.slice(0, middle);          //分割数组  
  var right = array.slice(middle);  
  return merge(mergeSort(left), mergeSort(right)); //递归合并与排序  
}  


function merge(leftArr, rightArr){  
  var result = [];  
  while (leftArr.length && rightArr.length){  
    if (leftArr[0] < rightArr[0])  
      result.push(leftArr.shift()); //把最小的最先取出，放到结果集中   
    else   
      result.push(rightArr.shift());  
  }   
  return result.concat(leftArr).concat(rightArr);  //剩下的就是合并，这样就排好序了  
}  

var arr = mergeSort([32,12,56,78,76,45,36]);
console.log(arr);   // [12, 32, 36, 45, 56, 76, 78]

桶排序

堆排序

希尔排序