算法复杂性概念

算法的复杂性（\(C\)）是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂度性（\(T\)），需要空间资源的量称为空间复杂性（\(S\)）。这个量应该是只依赖于要解的问题的规模（\(N\)）、算法的输入（\(I\)）和算法的本身（\(A\)）的函数，即\(C=F(N,I,A)\)。通常\(A\)隐藏在复杂性函数名当中，因而将\(C\)简写为\(C=(N,I)\)。

复杂性的计算

对于一个算法，\(N\)、\(I\)和\(A\)是已知的，现在的问题在于如何导出具体的\(C(N,I)\)数学表达式。下面以\(T(N,I)\)为例，将复杂性函数具体化。
设一台抽象计算机提供的元运算有\(k\)种，分别记为\(O_1,O_2,\cdots,O_k\)，每执行一次这些元运算所需要的时间分别为\(t_1,t_2,\cdots,t_k\)。对于给定的算法\(A\)，经统计，用到的元运算\(O_i\)的次数为\(e_i(i=1,2,\cdots,k)\)。对于每个\(i(1\leq i \leq k)\)，\(e_i\)是\(N\)和\(I\)的函数，即\(e_i=e_i(N,I)\)。因此有\(T(N,I)=\sum_{i=1}^kt_ie_i(N,I)\)，如前文所述，式中\(t_i(i=1,2,\cdots,k)\)是与\(N\)和\(I\)无关的常数。
到此我们得到了\(T(N,I)\)的一个相对具体的表达式。但是对一个算法，我们不可能对它的每个合法输入\(I\)都统计需要用到元运算次数\(e_i(i=1,2,\cdots,k)\)，因此\(T(N,I)\)的表达式需要进一步简化。既然我们不可能对于每个输入\(I\)都统计\(e_i(i=1,2,\cdots,k)\)，那我们可不可以只统计某些或者某类具有代表性的合法输入相应的\(e_i(i=1,2,\cdots,k)\)以此来评价其时间复杂性呢？
一般情况下，我们只考虑三种情况下的时间复杂度，即最坏情况、最好情况和平均情况下的时间复杂性，分别记为\(T_{max}(N)、T_{min}(N)和T_{avg}(N)\)。在数学上有
\(T_{max}(N)=max_{I{\in}D_N}T(N,T)=max_{I{\in}D_N}\sum_{i=1}^kt_ie_i(N,I)=\sum_{i=i}^kt_ie_i(N,I^*)=T(N,I^*)\)
\(T_{min}(N)=min_{I{\in}D_N}T(N,T)=min_{I{\in}D_N}\sum_{i=1}^kt_ie_i(N,I)=\sum_{i=i}^kt_ie_i(N,\tilde{I})=T(N,\tilde{I})\)
\(T_{avg}(N)=\sum_{I{\in}D_N}P(I)T(N,T)=\sum_{I{in}D_N}P(I)\sum_{i=1}^kt_ie_i(N,I)\)
式中，\(D_N\)是规模为\(N\)的合法输入的集合。~~翻译成人话~~前两个公式简单来说就是将\(D_N\)中使得\(T(N)\)可以达到最大、最小的值用于计算\(T(N)\)；第三个公式简单来说就是用输入规模的平均值来计算\(T(N)\)。以上三者可操作性最好且最有实际价值的是最坏情况下的时间复杂性。

复杂渐进性

当\(N\)单调增大且趋于\(\infty\)时，\(T(N)\)一般也将单调增大且趋于\(\infty\)。对于\(T(N)\)，如果存在\(\tilde{T}(N)\)，当\(N\rightarrow\infty\)时，使得\((T(N)-\tilde{T}(N))/T(N)\rightarrow0\)，就说\(\tilde{T}(N)\)是\(T(N)\)当\(N\rightarrow\infty\)时的渐进态，或称\(\tilde{T}(N)\)为算法\(A\)当\(N\rightarrow\infty\)时的渐进复杂性。~~说那么多废话~~其实在数学上就是\(\tilde{T}(N)=\lim\limits_{N\rightarrow\infty}T(N)\)；在直观上\(\tilde{T}(N)\)是\(T(N)\)略去低阶项留下的主项，所以\(\tilde{T}(N)\)一般比\(T(N)\)简单得多。
基于此，当\(\tilde{T}(N)\)存在时，我们用\(\tilde{T}(N)\)代替\(T(N)\)，这是对复杂性分析的一种简化比较，对于不同算法间时间复杂性的比较可以假设每个算法中用到的所有不同的元运算各执行一次所需要的时间都是一个单位时间，这样在就可以通过只比较\(\tilde{T}(N)\)的阶来判断算法时间复杂性优劣了。
对于渐进表达式还有以下四个记号\(O,\Omega,\theta和o\)，关于这方面我只简单说一下最常用的\(O\)~~其实是不会喵~~，想详细了解可以去看这里。
设\(f(N)和g(N)\)是定义在正数集上的正函数。如果存在正的常数\(C\)和自然数\(N_0\)，使得当\(N{\geq}N_0\)时有\(f(N){\leq}Cg(n)\)，则称函数\(f(N)\)当\(N\)充分大时有上界，且\(g(N)\)是它的一个上界，记为\(f(N)=O(g(N))\)。

例题

说到这里是不是还是很迷糊啊？没关系，看一下例子就明白啦！

1.分析\(3n^2+10n\)的渐进表达式

当\(n{\geq}10\)时，\(3n^2+10n{\leq}4n^2\)，所以\(3n^2+10n=O(n^2)\)，这里\(C=4\)。

2.分析算法时间复杂度

function sum(n){
    let sum = 0;
    let i = 1;
    for(i; i <= n; i++){
        console.log('test');
        for(let j = 1; j <= n; j++){
            sum = sum +  i * j;
        }
    }
    return sum;
}

该算法的问题规模为\(n\)。代码第二行赋值语句用了\(1\)个单位时间，第三行也用了\(1\)个单位时间，第四行用了\(n\)个单位时间，第五行用了\(n\)个单位时间，第六行用了\(n^2\)个单位时间，第七行用了\(n^2\)个单位时间，第十行用了\(1\)个单位时间。则\(T(N)=(2n^2+2n+3)\)，进一步简化为\(T(N)=O(n^2)\)。
其实平时算时间复杂度的时候不用这么繁琐，通常值看执行最多次的那条语句就可以了，因为\(O\)这种复杂度表示方法会忽略掉低阶、常量、系数，只需要记录一个最大的量级就可以。就比如这个例子执行最多次的代码语句为第七行，它用了\(n^2\)个单位时间，所以\(T(N)=O(n^2)\)。