算法学习笔记-01

复杂度分析浅析

一、为什么需要复杂度分析

可能平常,都会通过统计、监控,来得到相关的性能数据,来评估性能。有人将这种平时使用的性能分析方式,称为:事后分析法

但是事后分析法,虽然普遍存在,但其有一些缺陷:

  1. 测试结果非常依赖测试环境。
    • 某种意义上这也很方便,但是面对不同的机器、不同的编译环境,同段代码可能会有不同的结果。
  2. 测试结果受测试规模的影响很大。
    • 同段代码,在大规模和小规模下会有不一样的结果。

所以,能不能有一种方法,能让我们无视测试环境,在任意规模下都能较精确地分析出代码的性能呢?

自然是有的,那就是使用大O复杂度表示法运用时间复杂度空间复杂度来分析代码

二、大O复杂度表示法

大O表示法:算法的时间复杂度通常用大O符号表述,定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时,时间复杂度的极限情形称为算法的“渐近时间复杂度”。——百度百科

时间复杂度

时间复杂度:全称“渐进时间复杂度”,表示算法的执行时间与数据规模之间的增长关系。

我们这里用一个公式来表示:
$$
T(n) = O\left(f(n)\right)
$$

$T(n)$$n$$f(n)$$O$
代码的执行时间代码的规模每行代码的执行次数$T(n)$与$f(n)$成正比关系

为了更方便理解这个公式,我举一个例子:

#include <stdio.h>
int main(){
    int c = 0;
    for(int i=1; i<=n; ++i)
        c += i;

    return 0;
}

从 CPU 的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样,但是,我们这里只是粗略估计,所以可以假设每行代码执行的时间都一样,为 unit_time。在这个假设的基础之上,这段代码的总执行时间是多少呢?

第 3 行代码需要 1 个 unit_time 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2n * unit_time 的执行时间,所以这段代码总的执行时间就是 (2n+1) * unit_time。可以看出来,所有代码的执行时间 T(n) 与每行代码的执行次数成正比

时间复杂度的分析方法

1、只关注循环次数最多的一段代码

这里有一条目前我觉得很重要的推断:由于低阶、系数和常量均不影响规模大小,所以$f(n)$取最高阶代表即可。

2、加法法则

总复杂度等于量级最大的那段代码的复杂度

我们举一个例子:

#include <stdio.h>
int main(){
    int x=0;
    for(int i=1; i<=100; ++i)
        x += i;

    int y=0;
    for(int i=1; i<=n; ++i)
        x += i;

    int z=0;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j)
            z += j;
    }

    printf("%d %d %d\n", x, y, z);
    return 0;
}

在这个例子中,要求x,y,z。我们分别求出每个部分的时间复杂度,然后取最高阶的作整段代码的复杂度。

求x的这段,它会循环100次。由于是常数,所以不作数。

求y的这段,它会循环n次。记$O(n)$

求z的这段,它会循环$n^2$次。记$O(n^2)$。我们从中取最高阶$O(n^2)$作为整段代码的复杂度。

所以将加法公式化作表达式就为:

$$
\because T_1(n)=O(f(n)), T_2(n)=O(g(n))\\
\therefore T_总(n)=T_1(n)+T_2(n)=max(O(f(n))\\
\\
O(g(n)))=O(max(f(n),g(n)))
$$

3、乘法法则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

我们举个例子:

#include <stdio.h>
int f(int n);
int main(){
    int x = 0;
    for(int i=0;i<=n;++i)
        x += f(i);

    return 0;
}

int f(int n){
    int y = 0;
    for(int i=0;i<=n;++i)
        y += i;

    return y;
}

在这个例子中,如果我们把f()看作一个普通操作,那么第6行的时间复杂度就是$T_1(n)=O(n)$。但是f()是一个函数,它的时间复杂度为$T_2(n)=O(n)$,所以,这段代码的时间复杂度应该是,$ T_总=T_1(n) * T_2(n)=O(n * n)=O(n^2)$。

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

复杂度量级

其中,我们可以将其分为两类:多项式量级非多项式量级。非多项式量级只有两个:$O(2^n)$和$O(n!)$。

我们把时间复杂度为非多项式量级的算法问题叫做NP问题。当数据规模n越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长。所以,非多项式时间复杂度的算法其实是非常低效的算法。

1、$O(1)$——常量级时间复杂度

* 这个‘1’只是一种表示方法。

只要代码的执行时间不随n的增大而增长,或者,一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是$O(1)$

2、$O(\log n)$、$O(n\log n)$——对数阶时间复杂度

* 可以把所有对数阶的时间复杂度都记作$O(\log n)$,$O(n\log n)$同理。

根据换底公式,对数之间是可以互相转换的,所以说,任意对数都可以转换成$Cf(n)$,其中$f(n)$为对数。而根据之间得到的结论,常数等不影响代码规模的可以忽略不计。所以在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为$O(\log n)$

3、$O(m+n)$、$O(m*n)$——两个数据规模的时间复杂度

一般的,由两个数据的规模来决定的代码的复杂度,由于无法事先评估谁的量级大,所以我们在表示复杂度的时候,不能简单地利用加法法则,省略掉其中一个。所以,我们用$O(m+n)$、$O(m*n)$来表示。

那么,在这种情况下,加法法则应该为:

$$
\because T_1(m)=O(f(m)), T_2(n)=O(g(n))\\
\therefore T_总(n)=T_1(m)+T_2(n)=O(f(n)+g(n))
$$

而乘法法则不变。

空间复杂度分析

空间复杂度,全称渐进空间复杂度表示算法的存储空间与数据规模之间的增长关系

我们用一个例子来看一看。

#include <stdio.h>
int main(){
    int a[n];
    for(int i=0; i<=n; ++i)
        a[i] = i * i;
    for(int i=n-1; i>=0; --i)
        pritntf("%d", a[i]);

    return 0;
}

那么,分析这段代码,第三行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是$O(n)$。

三、内容小结

复杂度也叫渐进复杂度,包括时间复杂度空间复杂度,用来分析算法执行效率与数据规模之间的增长关系,可以粗略地表示,越高阶复杂度的算法,执行效率越低。常见的复杂度并不多,从低阶到高阶有$O(1)$、$O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$。

各常见复杂度中T(n)与n的正比关系

参考文章

MathJax基本的使用方式

数据结构与算法之美——王争


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!