排序算法、斐波那契、尾调用优化

作者: 张Piers | 来源:发表于2019-12-22 10:57 被阅读0次

时间复杂度

我们假设计算机运行一行基础代码需要执行一次运算。

aFunc() {
    console.log("Hello, World!");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

那么上面这个方法需要执行 2 次运算

bFunc(n) {
    for(let i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        console.log("Hello, World!");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算。

我们把算法需要执行的运算次数用输入大小n 的函数表示，即 T(n) 。
此时为了估算算法需要的运行时间和简化算法分析，我们引入时间复杂度的概念。

时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

所以上面的两个方法的时间复杂度是：T(n)也就是O(f(n))
时间复杂度比较

显然如果 f(n) = n^2，那么 T(n) = O(n^2)，f(n) = O(n^3)，T(n) = O(n^4) 都是成立的，但是因为第一个 f(n) 的增长速度与 T(n) 是最接近的，所以第一个是最好的选择，所以我们说这个算法的复杂度是 O(n^2) 。

如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。称此为大O推导法。

aFunc(n) {
    for(let i = 0; i < n; i++) {         // 循环次数为 n
        console.log("Hello, World!");      // 循环体时间复杂度为 O(1)
    }
}

此时时间复杂度为 O(n × 1)，即 O(n)。

对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。

aFunc(n) {
    for(let i = 0; i < n; i++) {         // 循环次数为 n
        for(let j = 0; j < n; j++) {       // 循环次数为 n
            console.log("Hello, World!");      // 循环体时间复杂度为 O(1)
        }
    }
}

此时时间复杂度为 O(n × n × 1)，即 O(n^2)。

对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。

aFunc(n) {
    // 第一部分时间复杂度为 O(n^2)
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            console.log("Hello, World!");
        }
    }
    // 第二部分时间复杂度为 O(n)
    for(j = 0; j < n; j++) {
        console.log("Hello, World!");
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。

aFunc(n) {
    if (n >= 0) {
        // 第一条路径时间复杂度为 O(n^2)
        for(let i = 0; i < n; i++) {
            for(let j = 0; j < n; j++) {
                console.log("输入数据大于等于零");
            }
        }
    } else {
        // 第二条路径时间复杂度为 O(n)
        for(let j = 0; j < n; j++) {
            console.log("输入数据小于零\n");
        }
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

最后，我们来练习一下

一. 基础题
求该方法的时间复杂度

aFunc(n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            printf("Hello World\n");
        }
    }
}

参考答案：
当 i = 0 时，内循环执行 n 次运算，当 i = 1 时，内循环执行 n - 1 次运算……当 i = n - 1 时，内循环执行 1 次运算。
所以，执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
根据上文说的大O推导法可以知道，此时时间复杂度为 O(n^2)。

二. 进阶题
求该方法的时间复杂度

aFunc(n) {
    for (let i = 2; i < n; i++) {
        i *= 2;
        console.log(i);
    }
}

参考答案：
假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。

三. 再次进阶
求该方法的时间复杂度

aFunc(n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

参考答案：
显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可知,树的高度为n,一棵高度为n的满二叉树的节点个数为2^n-1,当然,上图中的树肯定不是满二叉树,但也可以看出来,该树的节点个数
大于满二叉树节点数的一半,即（2^{n-1)/2,设计算次数为T(n),可知(2}n-1)/2 < T(n) < 2^n-1.
因此该算法的时间复杂度为O(2^n)

image

排序算法

image

冒泡排序（Bubble Sort）

算法描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法实现：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。

function bubbleSort(arr) {
    var len = arr.length;
    console.time('冒泡排序耗时');
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    console.timeEnd('冒泡排序耗时');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

选择排序（Selection Sort）

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

算法实现：

初始状态：无序区为R[1..n]，有序区为空；
第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个的新无序区；
n-1趟结束，数组有序化了。

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    console.time('选择排序耗时');
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

image

插入排序（Insertion Sort）

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

算法实现：

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

function insertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        console.time('插入排序耗时：');
        for (var i = 1; i < array.length; i++) {
            var key = array[i];
            var j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        console.timeEnd('插入排序耗时：');
        return array;
    } else {
        return 'array is not an Array!';
    }
}

// 优化 查找插入位置时使用二分查找
function binaryInsertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        console.time('二分插入排序耗时：');
        for (var i = 1; i < array.length; i++) {
            var key = array[i], left = 0, right = i - 1;
            while (left <= right) {
                var middle = parseInt((left + right) / 2);
                if (key < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            for (var j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            array[left] = key;
        }
        console.timeEnd('二分插入排序耗时：');

        return array;
    } else {
        return 'array is not an Array!';
    }
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

image

希尔排序（Shell Sort）

1.算法描述：
1959年Shell发明；第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。

算法实现：

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

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    console.time('希尔排序耗时:');
    while(gap < len/5) {          //动态定义间隔序列
        gap =gap*5+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/5)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    console.timeEnd('希尔排序耗时:');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

快速排序（Quick Sort）

1.算法描述：
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一。
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法实现：

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

/*方法说明：快速排序
@param  array 待排序数组*/
//方法一
function quickSort(array, left, right) {
    console.time('1.快速排序耗时');
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {
        if (left < right) {
            var x = array[right], i = left - 1, temp;
            for (var j = left; j <= right; j++) {
                if (array[j] <= x) {
                    i++;
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            quickSort(array, left, i - 1);
            quickSort(array, i + 1, right);
        }
        console.timeEnd('1.快速排序耗时');
        return array;
    } else {
        return 'array is not an Array or left or right is not a number!';
    }
}

//方法二
var quickSort2 = function(arr) {
    console.time('2.快速排序耗时');
    if (arr.length <= 1) { return arr; }
      var pivotIndex = Math.floor(arr.length / 2);
      var pivot = arr.splice(pivotIndex, 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]);
        }
      }
    console.timeEnd('2.快速排序耗时');
    return quickSort2(left).concat([pivot], quickSort2(right));
};

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

image

Q1:Array数组的flat方法实现

Array的方法flat很多浏览器还未能实现，请写一个flat方法，实现扁平化嵌套数组，如：

var arr1 = [1, 2, [3, 4]];
arr1.flat(); 
// [1, 2, 3, 4]

一般解答：

Array.prototype.flat = function() {
    var arr = [];
    this.forEach((item,idx) => {
        if(Array.isArray(item)) {
            arr = arr.concat(item.flat()); //递归去处理数组元素
        } else {
            arr.push(item);   //非数组直接push进去
        }
    })
    return arr;   //递归出口
}
let arr = [[2],[[2,3],[2]],3,4];
arr.flat(); // [2, 2, 3, 2, 3, 4]

牛逼解答：

arr.prototype.flat = function() {
    this.toString().split(',').map(item=> +item )
}

Q2: 爬楼梯问题

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
分析：这个问题要倒过来看，要到达n级楼梯，只有两种方式，从（n-1）级或（n-2）级到达的。所以可以用递推的思想去想这题，假设有一个数组s[n], 那么s[1] = 1（由于一开始就在第一级，只有一种方法）， s[2] = 1（只能从s[1]上去没有其他方法）。
那么就可以推出s[3] ~ s[n]了。
下面继续模拟一下， s[3] = s[1] + s[2]，因为只能从第一级跨两步，或者第二级跨一步。

function cStairs(n) {
    if(n === 1 || n === 2) {
        return 1;
    } else {
        return cStairs(n-1) + cStairs(n-2)
    }
}

实际的代码千万不要这么写没有优化过的菲波切细函数，原因参考阮一峰的尾调用优化

Q3: 二分查找

二分查找，是在一个有序的序列里查找某一个值，与小时候玩的猜数字游戏非常像

A: 0 ~ 100 猜一个数字
B: 50
A: 大了
B: 25
A: 对头，就是25

思路：

设定区间,low和high
找出口：找到target，返回target；
否则寻找，当前次序没有找到，把区间缩小后递归

function binaryFind(arr,target,low = 0,high = arr.length - 1) {
    const n = Math.floor((low+high) /2);
    const cur = arr[n];
    if(cur === target) {
        return `找到了${target},在第${n+1}个`;
    } else if(cur > target) {
        return binaryFind(arr,target,low, n-1);
    } else if (cur < target) {
        return binaryFind(arr,target,n+1,high);
    }
    return -1;
}

// 优化
function binaryFind(arr, target) {
    var low = 0,
        high = arr.length - 1,
        mid;
    while (low <= high) {
        mid = Math.floor((low + high) / 2);
        if (target === arr[mid]) {
            return `找到了${target},在第${mid + 1}个`
        }
        if (target > arr[mid]) {
            low = mid + 1;
        } else if (target < arr[mid]) {
            high = mid - 1;
        }
    }
    return -1
}

在我们的某个项目里抠出来的一段代码


for (let index = 0; index < this.list.length; index++) {
    let thisStart=this.list[index].StartDateTime;
    let thisEnd=this.list[index].EndDateTime;
    for (let nextIndex =index+1; nextIndex < this.list.length; nextIndex++) {
        let nextStart=this.list[nextIndex].StartDateTime;
        let nextEnd=this.list[nextIndex].EndDateTime;
        let thisStartBetween=moment(thisStart).isBetween(moment(nextStart), moment(nextEnd));
        let thisEndBetween=moment(thisEnd).isBetween(moment(nextStart), moment(nextEnd));
        let nextStartBetween=moment(nextStart).isBetween(moment(thisStart), moment(thisEnd));
        let nextEndBetween=moment(nextEnd).isBetween(moment(thisStart), moment(thisEnd));
        if (thisStartBetween||thisEndBetween||nextStartBetween||nextEndBetween||thisStart===nextStart||thisEnd===nextEnd) {
            Toptip.error(i18n.t('leaveExceptionFrom', {ref:index+1})+i18n.t('leaveExceptionTo', {ref:nextIndex+1}));
            return;
        }
    }
}

优化1: 无重叠区间

let list = [
    {
        startDate: '2019-11-12 09:00',
        endData: '2019-11-12 12:00'
    },
    {
        startDate: '2019-11-13 09:00',
        endData: '2019-11-13 12:00'
    },
    {
        startDate: '2019-11-13 22:00',
        endData: '2019-11-14 08:00'
    },
    {
        startDate: '2019-11-14 09:00',
        endData: '2019-11-14 17:00'
    },
    {
        startDate: '2019-11-11 22:00',
        endData: '2019-11-12 10:00'
    },
    {
        startDate: '2019-11-14 10:00',
        endData: '2019-11-14 12:00'
    },
];
let startArr = [];
let endArr = [];
list.forEach(item => {
    startArr.push(item.startDate);
    endArr.push(item.endData);
});
startArr = startArr.sort();
endArr = endArr.sort();
startArr.forEach((obj, index) => {
    if(startArr[index+1] < endArr[index]) {
        console.log('有重叠');
        return false;
    }
});

优化2: 合并区间
)，然后比较区间差总和

let merge=(intervals) => {
    intervals.sort((a,b)=>{
        //先排序
        if(a[0]!=b[0]){return a[0]-b[0]}
        return a[1]-b[1]
    })
    let len=intervals.length
    let res=[],start,end
    for(let i=0;i<len;i++){
        let s=intervals[i][0],e=intervals[i][1]
        if(!start) {start=s,end=e}
        else if(s<=end){end=Math.max(end,e)}
        else{
            let part=[start,end]
            res.push(part)
            start=s
            end=e
        }
    }
    if(start){
        let part=[start,end]
        res.push(part)
    }
    return res
}
let arr=[
[1,3],[2,6],[8,10],[9,11]]

console.log(merge(arr)) //[1,6],[8,11]

排序算法、斐波那契、尾调用优化

时间复杂度

排序算法

冒泡排序（Bubble Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

希尔排序（Shell Sort）

快速排序（Quick Sort）

Q1:Array数组的flat方法实现

Q2: 爬楼梯问题

Q3: 二分查找

在我们的某个项目里抠出来的一段代码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读