复杂度表示方法

大O符号(Big O natation),也叫渐进符号

常见复杂度:

  • O(1):常熟复杂度
  • O(logn):对数复杂度
  • O(n):线性时间复杂度
  • O(n2):平方
  • O(nlogn):nlog
  • O(n3):立方
  • O(2n):指数
  • O(n!):阶乘

其中括号中的N在表达式中是不用系数的,比如一端代码执行2n次,那这个算法度是O(n),而不会说是O(2n),同理其他几个也一样,O(1)只是表示执行常数次(2次,3次…)。另外只看最高复杂度的运算。

常见复杂度的曲线图

复杂度曲线

代码复杂度

有时间和空间两个考量维度

  • 时间维度:是指执行当前算法所消耗的时间,对应时间复杂度
  • 空间维度:是指执行当前算法需要占用多少内存空间,对应空间复杂度

1. 时间复杂度

对于算法输入n,代码需要执行多少次可以计算得到结果。

举几个具体例子:

// 复杂度O(1)
function test(x) {
    let sum = 0;
    sum = x * (x + 1) / 2;
    return sum;
}
// 复杂度O(n); 2n依旧是n
function test(x) {
    let sum = 0;
    for(let i=0; i <= sum; i++) {
        sum += i;
    }
    for(let j=0; j <= sum; j++) {
        sum += i;
    }
    return sum;
}
// 复杂度O(n^2)
function bubbleSort(arr) {
    let temp;
    let len = arr.length;
    for(let i=0; i < n-1; i++) {
        for(let j=0; j < n-1-j; j++) {
            if(arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

再比如:

// 复杂度O(nlogn)
for(m=1; m<n; m++) {
    i = 1;
    while(i<n) {
        i = i * 2;
    }
}

另外算法复杂度分析时候,有个主理论需要了解下,用来推导递归算法的复杂度,算是一块奠基石。如果对具体的数学推导不感兴趣的话,就重点关注下应用举例:

Master theorem

2. 空间复杂度

对于算法输入n,得到计算结果需要开辟多少存储空间,与n是否具有倍数关系,取最大值。常见有O(1),O(n),O(logn)

如果代码的执行所需要分配的内存不会根据n变化,就是常数复杂度O(1)。

对于存在n倍关系的,有两个常用观察点:数组和递归深度。
比如使用一个一维数组,复杂度就是O(n),二维数组就是O(n^2);
对于递归:复杂度就是递归深度*每次递归所需要的辅助空间复杂度。

空间复杂度问题在大部分会出现在算法边界问题上,比如数值过大,存储空间限制等等,这类场景需要综合考虑时间复杂度和空间复杂度。

有些场景可以使用空间复杂度来大幅降低时间复杂度问题,比如使用缓存技术解决斐波那契数列递归算法(可参考爬楼梯算法问题)。

&Next

了解算法复杂度之后对于算法分析就有了实质的工具,对确定优化方向会很有帮助。日常写代码顺手算一哈。

avatar
  Subscribe  
提醒