# 复杂度分析

# 为什么评估算法?

  • 执行效率关乎时间成本
  • 存储空间关乎硬件成本

数据结构和算法本身解决的是“快”和“省”的问题

# 如何评估算法

# 事后统计法

通过统计、监控,就能得到算法执行的时间和占用的内存大小,这种统计法有非常大的局限性

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

# 大 O 复杂度表示法

一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法

# 例一

int cal(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; ++i) {
          sum = sum + i;
    } 
    return sum; 
}

从 CPU 的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。 尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样,我们这里假设每行代码执行的时间都一样为 unit_time

  • unit_time
    • 2、3 行
  • n * unit_time
    • 4、5 行
  • 总时间
    • T(n) = (2n+2)*unit_time
    • 即:y = k * x

可以看出所有代码的执行时间 T(n) 与每行代码的执行次数成正比

# 例二

int cal(int n) {
    int sum = 0; 
    int i = 1; 
    int j = 1; 
    for (; i <= n; ++i) { 
        j = 1; 
        for (; j <= n; ++j) {
            sum = sum + i * j; 
        } 
    } 
}
  • unit_time
    • 2、3、4 行
  • n * unit_time
    • 5、6 行
  • n * n * unit_time
    • 7、8 行
  • 总时间
    • T(n) = (2n^2 +2n + 3)*unit_time
    • 即:y = x^2 + x + k

可以看出所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

# 大O时间复杂度上场

我们根据这个规律总结成一个公式:T(n) = O(f(n))

  • T(n): 代码执行的时间
  • n: 表示数据规模的大小
  • f(n): 表示每行代码执行的次数总和
  • O: 表示代码的执行时间 T(n) 与 f(n) 表达式成正比

大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度

当 n 很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。如果用大 O 表示法表示刚讲的那两段代码的时间复杂度,就可以记为:T(n) = O(n); T(n) = O(n^2)

时间复杂度-百度百科 时间复杂度-维基百科

# 时间复杂度分析

  • 时间复杂度 常见的时间复杂度

# 空间复杂度分析

  • 只关注循环执行次数最多的一段代码
  • 加法法则:总复杂度等于量级最大的那段代码的复杂度
  • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度实例分析

  • O(1)
  • O(logn)、O(nlogn)
  • O(m+n)、O(m*n)

# 四个维度的复杂度分析

# 例一

分析下面代码的时间复杂度

// n表示数组array的长度
int find(int[] array, int n, int x) 
{ 
    int i = 0;
    int pos = -1; 
    for (; i < n; ++i) 
    { 
        if (array[i] == x) 
            pos = i; 
    } 
    return pos;
}
  • 复杂度是 O(n)

简单优化一下代码

// n表示数组array的长度
int find(int[] array, int n, int x)
{ 
    int i = 0; 
    int pos = -1; 
    for (; i < n; ++i) 
    { 
        if (array[i] == x) 
        { 
            pos = i; 
            break; 
        } 
    }
    return pos;
}
  • 时间复杂度

    • 如果数组中第一个元素正好是要查找的变量 x,那时间复杂度就是 O(1)。
    • 但如果数组中不存在变量 x,那我们就需要把整个数组都遍历一遍,时间复杂度就成了 O(n)。
  • 最好情况时间复杂度

    • 最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度
    • 即第一个元素就是要查找的元素
  • 最坏情况时间复杂度

    • 最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度
    • 需要把整个数组都遍历一遍
  • 平均情况时间复杂度

    要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值,即: 平均情况时间复杂度

    • 以上结论并非如此完全正确,需加上一些概率论的知识

      我们知道,要查找的变量 x,要么在数组里,要么就不在数组里。这两种情况对应的概率统计起来很麻烦。我们假设在数组中与不在数组中的概率都为 1/2。另外,要查找的数据出现在 0~n-1 这 n 个位置的概率也是一样的,为 1/n。所以,根据概率乘法法则,要查找的数据出现在 0~n-1 中任意位置的概率就是 1/(2n) 平均情况时间复杂度加概率

    • 这个值就是概率论中的加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度
    • 加权平均时间复杂度O((3n+1)/4)去系数后仍然是O(n)

# 例二

// array表示一个长度为n的数组 
// 代码中的array.length就等于n 
int[] array = new int[n]; 
int count = 0; 
void insert(int val) 
{ 
    if (count == array.length) 
    { 
        int sum = 0; 
        for (int i = 0; i < array.length; ++i) 
        { 
            sum = sum + array[i]; 
        } 
        array[0] = sum; 
        count = 1; 
    } 
    array[count] = val; 
    ++count;
}

当数组满了之后,也就是代码中的 count == array.length 时,我们用 for 循环遍历数组求和,并清空数组,将求和之后的 sum 值放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空闲空间,则直接将数据插入数组。

  • 最好时间复杂度 O(1)
  • 最坏时间复杂度 O(n)
  • 加权平均复杂度 O(1) 加权平均复杂度
  • 例子
    • 例一 是find()查询方法
      • 在极端情况下,复杂度才为 O(1)
    • 例二 是insert()插入方法
      • 在大部分情况下,时间复杂度都为 O(1)。
      • O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入,出现的频率是非常有规律的,而且有一定的前后时序关系,一般都是一个 O(n) 插入之后,紧跟着 n-1 个 O(1) 的插入操作,循环往复。
      • 每一次 O(n) 的插入操作,都会跟着 n-1 次 O(1) 的插入操作,所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是 O(1)。
  • 均摊时间复杂度
    • 均摊时间复杂度应用的场景比平均复杂度更加特殊、更加有限
    • 均摊时间复杂度就是一种特殊的平均时间复杂度

# 例三

// 全局变量,大小为10的数组array,长度len,下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) 
{ 
    if (i >= len) 
    { 
        // 数组空间不够了 
        // 重新申请一个2倍大小的数组空间 
        int new_array[] = new int[len*2]; 
        // 把原来array数组中的数据依次copy到new_array 
        for (int j = 0; j < len; ++j) 
        { 
            new_array[j] = array[j]; 
        } 
        // new_array复制给array,array现在大小就是2倍len了 
        array = new_array; 
        len = 2 * len; 
    }
    // 将element放到下标为i的位置,下标i加一 
    array[i] = element; 
    ++i;
}
  • add()新增函函数
    • 最好时间复杂度是O(1)
    • 最差时间复杂度是O(n)
    • 均摊时间复杂度是O(1)

评 论: