算法

发表于   |   分类于   |  

算法

常用算法

算法与数据结构

杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function generator(rows){
    let arr = [];
    if(rows<=0){
        return arr;
    }
    for(var i = 0;i<rows;i++){
        let subArr = [];
        for(var j = 0;j<=i;j++){
            if(j>0 && j<i){
                subArr.push(arr[i-1][j-1] + arr[i-1][j]);
            }else{
                subArr.push(1)
            }
        }
        arr.push(subArr);
    }
    return arr;
}

算法复杂度

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

为什么需要时间复杂度

在实际项目开发中,我们理想状态是写出的这段代码是最优的,但是总不能把所有实现方式都写出来,然后去作比较,所以需要一个指标去衡量这段代码的效率,并且直接跑代码一定的局限性:

  1. 测试结果受当前运行环境影响

    同样的代码,在不同的平台执行的时间明显不同

  2. 测试结果受测试数据的影响

    不同的测试数据可能会带来不同的结果,比如我们按顺序查找的方法查找数组的一个元素,如果这个元素刚好在第一位,则执行了一次,但在最后的话,就得执行整个数组

因此,我们就需要一个不受硬件,环境,数据影响的指标来去表示算法的执行效率,那就是算法的复杂度

时间复杂度表示

大O时间复杂度表示法

1
2
3
4
5
6
7
function func(n){
    let res = 1; // 执行一次
    for(let i = 1; i < n; i++){ // 执行n次
        res *= i; // 执行n-1次
    }
    return res; // 执行一次
}

上面代码为求n!,我们初略计算下上述代码需要执行的时间,首先为了方便计算,假设执行每一行代码的时间都是相同的,在这里假设,每行代码执行一次的时间为t,代码的总时间为T(n),因此就能得到上述代码的总执行时间:

1
T(n) = t + nt + (n - 1)t + t = (2n+1)t

我们以n为x轴,T(n)为y轴,因此就能得出结论: 代码总执行时间和每行代码执行的次数成正比,大O表示法就是用来表示这样的趋势,大O表示法表示代码执行时间随数据规模增长的一种变化趋势,下面就是大O表示法的公式:

1
T(n) = O(F(n))

  • n: 代表数据规模,相当于上面例子中的n

  • F(n): 表示代码执行次数的总和,代码执行次数的总和与数据规模有关,所以用F(n)表示,F(n)对应上面例子中的

    ( 2n + 1 )

  • T(n): 代表代码的执行时间,对应上面例子中的T(n)

  • O: 大O用来表示代码执行时间T(n) 与 代码执行次数总和F（n）之间的正比关系。

上面说过大O表示法表示代码执行时间随数据规模增长的一种变化趋势,只代表趋势,不是实际执行的时间,当公司中的n无穷大时,系数和常数就可以忽略不计,所以忽略掉以后,大O表示法就变为:

1
T(n) = O(n)

至此,我们就知道了什么是大O表示法以及怎么用大O表示法来表示时间复杂度,在看个例子,分析下代码的时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function func(arr){
    let n = arr.length; // 执行一次
 	let i = 0; // 执行一次
    for(; i< n - 1; i++){ //执行n次
        let j = 0;// 执行n次
        for(; j < n - 1; j++){ // 执行n次
            if(arr[j]>arr[j+1]){// 执行n*n次
                var temp = arr[j];
            	arr[j] = arr[j+1];
            	arr[j+1] = temp;
            }
        }
    }
    return arr;
}

以上代码为最差的冒泡排序,先不管算法是否最优,只为分析时间复杂度,执行这段代码的时间复杂度为:

1
T(n) = t + t + nt + nt + nt + (n*n)t + (n*n)t = (2n²+3n+2)t = O(n²)

因此,我们通过两个例子可以发现时间复杂度大O规律:

  1. 不保留系数
  2. 只保留最高阶
  3. 嵌套代码的复杂度为内外代码复杂度的乘积

怎么分析一段代码的时间复杂度

通过上面的规律,可以得到,判断一段代码的时间复杂度,只需要关注这段代码执行次数最多的代码次数,其它都可忽略

常见的时间复杂度

最常见的时间复杂度有常数阶O(1),对数阶O(logn),线性阶O(n),线性对数阶O(nlogn),平方阶O(n²)

1
1 O(1) < O(logn) < O(n) < O(nlogn) < O(n²)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function func(arr,key){
    const n = arr.length;
    let low = 0;
    let high = n -1;
    let mid = Math.floor((low + high)/2);
    while(low<=high){
        mid = Math.floor((low + high)/2);// 执行次数
    	if(key === arr[mid]){
            return mid;
        }else if(key < arr[mid]){
        	high =  mid - 1;         
        }else{
            low = mid + 1
        }
    }
    return -1;
}

以上代码为二分查找的代码,二分查找法是一个高效的查找算法,现在分析下上边代码的复杂度,发现执行次数最多为第7行,所以算法复杂度为这句代码的执行次数,分析以上代码,最坏的打算就是一直一半查找,直到只剩一个数,或者数组中不存在要找的元素

1
2
3
4
第一次执行,剩余元素个数n/2
第二次执行,剩余元素个数n/2/2
... ...
第n次执行,剩余元素个数n/2^T = 1 <==> 2^T = n <=> log2n

以上代码用大O表示时间复杂度即为O(logn),省略常数

什么是对数?

对数符号

以a为底N的对数记作img, 对数符号log出自拉丁文logarithm，最早由意大利数学家卡瓦列里（Cavalieri）所使用。20世纪初，形成了对数的现代表示。为了使用方便，人们逐渐把以10为底的常用对数及以无理数e为底的自然对数分别记作lgN和lnN。

对数的定义

如果 img ，即a的x次方等于N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作 img 。其中，a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”。

对数函数

定义
函数 img 叫做对数函数（logarithmic function），其中x是自变量。对数函数的定义域是 img 。

函数基本性质
1、过定点 img,即x=1时,y=0。
2、当img 时,在 img 上是减函数；当 img 时,在 img上是增函数。

空间复杂度

空间复杂度是指算法在计算机内执行时所需存储的度量

算法执行期间所需要的存储空间包括3个部分

  • 算法程序所占的空间；
  • 输入的初始数据所占的存储空间；
  • 算法执行过程中所需要的额外空间。

JavaScript常见算法

冒泡排序

冒泡排序,是一种最基本的排序算法。它重复地走访要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成

思想:

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bubbleSort(arr) {
    var i = arr.length, j;
    var tempExchangVal;
    while (i > 0) {
        for (j = 0; j < i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                tempExchangVal = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tempExchangVal;
            }
        }
        i--;
    }
    return arr;
}
 
var arr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
var arrSorted = bubbleSort(arr);

插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法,插入排序原理就像是打扑克,既在排好的顺序里插入到对应的位置

思想:

就是比大小，满足条件交换位置，一开始会像冒泡排序一样，但会比冒泡多一步就是交换后原位置会继续和前面的数比较满足条件交换，直到a[i+1]前面的数组是有序的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var arr = new Array(1, 3, 2, 8, 9, 1, 5);
//插入排序
function InsertionSort(arr) {
    if (arr == null || arr.length < 2) {
        return arr;
    }
    for (let i = 1; i < arr.length; i++) {
        for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            let temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
    return arr;
}
//控制台输出
InsertionSort(arr);

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进

挖坑填数法+分冶法

分冶法:

  • 1．先从数列中取出一个数作为基准数。
  • 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  • 3．再对左右区间重复第二步，直到各区间只有一个数。

思想:

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var arr = new Array(1, 3, 2, 8, 9, 1, 5);
function Quicksort(arr,left = 0,right = arr.length-1) {
    if (left >= right) { //如果左边的索引大于等于右边的索引说明整理完毕
        return
    }
    let i = left;
    let j = right;
    const baseVal = arr[j]; // 取无序数组最后一个数为基准值
    while (i < j) { //把所有比基准值小的数放在左边大的数放在右边
        while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
            i++
        }
        arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
        while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
            j--
        }
        arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
    }
    arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
    Quicksort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
    Quicksort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
	return arr
}
Quicksort(arr);

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function　merge(left, right){
    console.log(left,right)
    var　result=[];
    while(left.length>0 && right.length>0){
        if(left[0]<right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return　result.concat(left).concat(right);
}
function　mergeSort(items){
    if(items.length == 1){
        return　items;
	}
	var　middle = Math.floor(items.length/2),
    left = items.slice(0, middle),
    right = items.slice(middle);
    return　merge(mergeSort(left), mergeSort(right));
}
mergeSort([2,4,7,5,8,1,3,6])

选择排序

选择排序工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var arr = new Array(1, 3, 2, 8, 9, 1, 5);
function SelectionSort(arr) {
    if (arr == null || arr.length < 2) {
         return arr;
    }
    for (var i = 0; i < (arr.length - 1); i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
SelectionSort(arr);

希尔排序

希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法(三层for循环+if)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
let arr = [9,2,1,4,3,7,5,8,6,0];
function sort(arr){
    if(arr == null || arr.length <= 1){
        return arr;
    }
    //希尔排序  升序 增量为5 2 1
    for (let d = Math.floor(arr.length / 2);d>0;d = Math.floor(d/2)) { 
        for (let i = d; i < arr.length; i++){ 
            //i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标 
            //j:代表与i同一组的数组元素角标
            for (let j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界
                if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标
                    //符合条件，插入元素（交换位置）
                    let temp = arr[j];
                    arr[j] = arr[j + d];
                    arr[j + d] = temp;
                }
            }
        } 
        console.log(arr);
        //[7, 2, 1, 4, 0, 9, 5, 8, 6, 3] 
        //[0, 2, 1, 3, 5, 4, 6, 8, 7, 9]
        //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
    return arr;
}
sort(arr);

堆排序

堆是基于树抽象数据类型的一种特殊的数据结构,一个常见的例子就是优先队列,还有排序算法之一的堆排序

最大堆: 父节点大于子节点

最小堆: 父节点小于子节点

计数排序

桶排序

基数排序

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

思想:

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如 果x <a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
    if (low <= high) {
        if (arr[low] == find) {
            return low;
        }
        if (arr[high] == find) {
            return high;
        }
        var mid = Math.ceil((high + low) / 2);
        if (arr[mid] == find) {
            return mid;
        } else if (arr[mid] > find) {
            return binary(find, arr, low, mid - 1);
        } else {
            return binary(find, arr, mid + 1, high);
        }
    }
    return -1;
}
binary(15, Arr, 0, Arr.length - 1);