实现某个需求的方式、算法有很多种。但是每种方式的效率是不同的。

    例如： 求100以内的所有正整数的和、积。

    方式一：一个一个运算，1+2+3+..+100
    方式二：使用累加公式计算

    明显方式一的占用时间、计算次数高于方式二，计算机科学用时间复杂度来衡量算法的效率。而衡量时间复杂度的指标为占用空间和运行时间。

    时间复杂度概念：

    若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。 记作 T(n)= O(f(n))，称 O(f(n))) 为算法的渐进时间复杂度，简称时间复杂度。

    前文学习了两种排序方式：冒泡排序和选择排序，我们来通过时间复杂度判断谁的效率高。

    时间复杂度计算原则：

    1. 如果运行时间是常数量级，用常数1表示；
    2. 只保留时间函数中的最高阶项；
    3. 如果最高阶项存在，则省去最高阶项前面的系数。

    冒泡排序

    1. let A = [2, 15, 7, 5, 215, 91];
    3. for (let m = 0; m < A.length; m++) {
    4.       let state = true;
    5.     for (let i = 0; i < A.length; i++) {
    6.         if (A[i] > A[i + 1]) {
    7.             let temp = A[i];
    8.             A[i] = A[i + 1];
    9.             A[i + 1] = temp;
    10.             state = false;
    11.         }
    12.     }
    13.     if(state) break;
    14. }
    16. console.log(A)

    从函数中可以看出：两层循环嵌套，也就是执行了 A.length*A.length 次 ，记数组长度为 n，那么冒泡排序所需的时间（程序执行次数）,T(n)= n**，根据计算原则T(n)存在最高阶项 n**，去掉系数，那么冒泡排序的时间复杂度为：O(n**)

    选择排序

    1. function selectionSort(arr) {
    2.     var len = arr.length;
    3.     var minIndex, temp;
    4.     for (var i = 0; i < len - 1; i++) {
    5.         minIndex = i;
    6.         for (var j = i + 1; j < len; j++) {
    7.             if (arr[j] < arr[minIndex]) {     // 寻找最小的数
    8.                 minIndex = j;                 // 将最小数的索引保存
    9.             }
    10.         }
    11.         temp = arr[i];
    12.         arr[i] = arr[minIndex];
    13.         arr[minIndex] = temp;
    14.     }
    15.     return arr;
    16. }

    从代码中可以看出一共遍历了n + n-1 + n-2 + … + 2 + 1 = n (n+1) / 2 = 0.5 n2 + 0.5 n，那么时间复杂度是O(n**2**)

    我们计算了两种排序的时间复杂度都为     O(n2**) ，说明两种算法效率相差不大。
    *
    当数列为由小到大的有序数列时为最好情况，当由大到小时为为最坏情况。最好情况是，已经有序，交换0次；而选择排序最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。因此，选择排序的效率要比冒泡排序的效率要高，但相差不大。

    ps：根据实际的比较，冒泡排序是所有排序方式中时间复杂度最大，也就是效率最低的。所以不推荐使用冒泡排序。