跳到主要内容

算法衡量

执行时间测量​

通过 console.time() console.timeEnd()​

console.time(2)
fun()
console.timeEnd(2);

通过 new Date()​

// 生成 10000 个整数
function gen() {
    const arr = [];
    for (let i = 0; i < 10000; i++) {
        arr[i] = i;
    }
    return arr;
}
// 数组随机打乱
function shuffle(array){
        for(let i=0;i<array.length-1;i++){
            // 从 [i,arr.length - 1] 中取一个整数
            const j=i+Math.floor(Math.random()*(array.length-i));
            [array[i],array[j]]=[array[j],array[i]];
        }
        return array
}
const start=new Date().getTime();
shuffle(gen())
const end=new Date().getTime();
console.log((end-start)+'ms');

时间频度​

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费的 时间就多

一个算法中语句执行次数成为 语句频度或时间频度。记为 T(n)

特点：

  • 忽略常数项 : 随着 n 变大，执行曲线无线接近，常数项可以忽略
  • 忽略低次项 ：随着 n 变大，执行曲线无限接近，低次项可以忽略
  • 忽略系数项 ：随着 n 变大, 执行曲线无线接近，系数项可以忽略（立方项时不可以忽略）

时间复杂度​

一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n) 的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度

计算​

  • 用常数项 1 代替运行时间中的所有加法常数

  • 修改后的运行次数函数中，只保留最高阶项

  • 去除最高阶项的系数

常见的时间复杂度​

  • 常数阶 O(1)

    无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就是 O(1)

    • 说明:

      int i=1;
      int j=2;
      ++i;
      j++;
      int m = i + j;

      上述代码在执行的时候，他消耗的时间并不随着某个变量的增长而增长，那么无论这类代码有多长， 即使有几万几十万行，都可以用 O(1) 来表示它的时间复杂度

  • 对数阶 O($\log_{2}{n}$)

    • 说明:

      int i=1;
      while(i<n){
          i=i*2
      }

      在 while 循环里面，每次都将 i2 ,乘完之后， i 距离 n 就越来越近了。假设循环 x 次之后，i 就 大于 n 了，此时这个循环退出了，也就是说 2 的 x 次方等于 n ,那么 x = $log_{2}{n}$ ,也就是说 当循环 $log_{2}{n}$ 次之后，这个代码就结束了，因此这个代码的时间复杂度为 O($log_{2}{n}$)。 O($log_{2}{n}$) 的这个 2 实际上是根据代码变化的,如果 i=i3 ， 则是 O($log_{3}{n}$)

  • 线性阶 O(n)

    • 说明：

      for(let i=1;i<=n;++i){
          j=i;
          j++
      }

      这段代码， for 循环里面的代码会执行 n 遍,因此它消耗的时间是随着 n 的变化而变化的 因此这类代码都可以用 O(n) 来表示它的时间复杂度

  • 线性对数阶 O(n$log_{2}{n}$)

    • 说明

      for(let i=1;i<n;i++){
          i=1;
          while(i<n>){
              i=i*2
          }
      }

      线性对数阶 O(n$log_{2}{n}$) 是说将时间复杂度为 O($log_{2}{n}$) 的代码循环 N 遍 的话，那么它的时间复杂度就是 N * O($log_{2}{n}$),也就是 O(n$log_{2}{n}$)

  • 平方阶 O($n^{2}$)

    • 说明

      for(let i=1;i<=n;i++){
          for(let j=1;j<=n;j++){
              j=i;
              j++
          }
      }

      平方阶 O($n^{2}$) ，把 O(n) 的代码再嵌套循环一遍，它的时间复杂度为 O($n^{2}$)。 这段代码其实就是嵌套了两层 n 循环，他的时间复杂度为 O(n*n)，即 O($n^{2}$)。如果 将其中的一层循环的 n 改为 m , 时间复杂度为 O(m*n)

  • 立方阶 O($n^{3}$)

  • k 次方阶 O($n^{n}$)

  • 指数阶 O($2^{n}$)

常见的算法时间复杂度由小到大依次为: O(1) < O($\log_{2}{n}$) < O(n) < O(n$log_{2}{n}$) < O($n^{2}$) < O($n^{3}$) < O($n^{n}$) < O($2^{n}$)

我们应该尽可能避免使用 指数阶 的算法

平均时间复杂度​

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间

最坏时间复杂度​

最坏情况下的时间复杂度成为最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的 时间复杂度。

这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限， 这就保证了算法的运行时间不会比最坏情况更长

空间复杂度​

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元。

在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的是程序执行的速度。 一些缓存的产品和算法本质就是用空间换时间