算法整理

[jinjiaxing]

时间复杂度

评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
每个算法中语句执行的次数叫做时间频度，叫T(n)
O(f(n))=时间复杂度。
O(f(n)中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶

计算法则：
1.用常数1来取代运行时间中所有加法常数。
2.修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常用的时间复杂度按照耗费的时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

常用算法时间复杂度：

排序

1. 快排
   • 思路：
     • 找一个基点（第一个，中间，或者最后一个都可以）
     • 数组中小于这个基点的元素，放入左数组
     • 数组中大于这个基点的元素，放入右数组
     • 递归
   • 时间复杂度：O(nlogn)
   • 属于交互排序，且是不稳定排序

function quickSort(arr) {
    if(arr instanceof Array == false) {
        return null;
    }
    if(arr && arr.length <=1) {
        return arr;
    }

    let basePoint = arr[0];
    let leftArr = [];
    let rightArr = [];
    arr.forEach((item,index)=>{
        if(index !==0) {
            if(item<basePoint) {
                leftArr.push(item);
            } else if(item>basePoint) {
                rightArr.push(item);
            }
        }
    });

    return quickSort(leftArr).concat([basePoint]).concat(quickSort(rightArr));
}

2.冒泡排序

• 思路：
  • 通过依次比较、交换相邻的元素大小（按照由小到大的顺序，如果符合这个顺序就不用交换）
  • 双层循环
    • 外层控制循环次数，次数=数组长度，
    • 内层循环比较交换位置,每轮循环结束后，最大值放在最右边
  • 时间复杂度：O(n^2)

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

3. 选择排序

• 思路：
  • 找到数组中最小值，替换到数组中第0个位置
  • 继续寻找最小值的，替换到数组中第1个位置
  • 找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推
  • 时间复杂度：O(n^2)

 function selectSort(array){
    let length = array.length;
    let minIndex;
    for (var i=0; i<length-1; i++){     
        minIndex = i;                          
        for (var j=i; j<length; j++ ){ 
            if (array[j]<array[minIndex]){ 
               minIndex = j;
            }
        }
        [array[i],array[minIndex]] = [array[minIndex],array[i]];
    }
    return array;
};