时间复杂度

一个算法的执行时间大致等于其所有语句执行时间的总和,而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积.
一条语句的重复执行次数乘坐语句的频度(Frequency Count).
设每条语句执行一次所需的时间为单位时间,则一个算法的执行时间就是该算法中所有语句频度之和.

for(int i=0;i<n;++i){                        //频度n+1
    for(int j=0;j<n;++j){                    //频度n*(n+1)
        c[i][j]=0;                           //频度n*n
        for(int k=0;k<n;++k){                //频度n*n*(n+1)
            c[i][j]=c[i][j]+a[i][j]*b[k][j]; //频度n*n*n
        }
    }
}

因此以上算法所有语句的频度之和,即为算法的执行时间,用T(n)表示:

{{T(n) = 2n^3+3n^2+2n+1}}

求解的输入量称之为规模,一般用n表示.以上求解式,当n趋于无限大时,则有:

{{\displaystyle\lim_{x \to \infty} \dfrac{T(n)}{n^3} = \displaystyle\lim_{x \to \infty} \dfrac{(2n^3 + 3n^2 + 2n + 1)}{n^3} = 2}}

我擦,latex好难用.

当n充分大时,则T(n)与n^3之比为一个不等于0的常数.即T(n)与n^3为同数量级,数量级通常由O表示.

当问题规模的趋向无限大时,T(n)的数量级称为算法的渐近时间复杂度,通常表示为:

{{T(n) = O(f(n))}}

以上矩阵乘积算法的渐近时间复杂度则记作:

{{T(n)=O(n^3)}}

如果算法的执行时间不随着问题规模n的增加而增长,算法中语句的频度就是某个常数,则此常数再大,算法的时间复杂度都是:

{{O(1)}}

对于循环语句只需考虑循环体中语句执行次数,当有若干个循环语句时,算法的时间复杂度是由嵌套的层次中最深的内层语句所决定的.

算法的时间复杂度不仅和问题的规模大小有关,还与问题数据的初始状态有关,因此就有了算法在最好/最坏以及平均状态下的时间复杂度概念.

算法在最好情况的情况下的时间复杂度是指算法计算量的最小值,而最坏情况下的时间复杂度则是算法计算量的最大值,平均情况下的时间复杂度是指算法在所有可能情况下的计算量经过加权得出的平均值.

常见的时间复杂度按照数量级排序依次为:
1.常数阶:{{O(1)}}
2.对数阶: {{O(\log_2 n)}}
3.线性阶: {{O(n)}}
4.线性对数阶: {{O(n\log_2 n)}}
5.平方阶: {{O(n^2)}}
6.立方阶: {{O(n^3)}}
7.k次方阶: {{O(n^k)}}
8.指数阶: {{O(2^n)}}

空间复杂度

对于算法的存储空间的需求,类似于算法的时间复杂度,采用渐近空间复杂度作为算法的存储空间的度量,简称空间复杂度,记作:

{{S(n) = O(f(n))}}

一个算法在执行时候,除了必要的指令/常数/变量/和输入数据外,还有对数据进行操作额外的辅助存储空间.

对于输入数据所占的具体存储量取决于问题本身,与算法无关,这样只需分析算法在实现时所需的辅助空间即可.若执行时辅助空间相遇输入数据而言是常数,则此算法的空间复杂度为:

{{O(1)}}