数据结构 时间复杂度

时间复杂度T(n)

1.定义：

算法的时间复杂度是指，算法的执行时间和语句的频度。

执行时间：即算法的执行时间，算法中所有语句执行时间的总和，即语句的重复次数与执行一次所需的时间的乘积。

一条语句的执行次数称为语句频度;

for (int i = 0; i < n; i++) {    //频度 n+1
    for (int k = 0; k < n; k++) {  //频度 n*(n+1)

        int m = i + k;   //频度 n*n
        for (int j = 0; j < n; j++) {  //频度 n*n(n+1)
            Log.e("MM", "jj:>>>" + j);//频度 n*n*n

        }
    }
}

算法中所有语句的频度之即算法的执行时间用T（n）表示：
    T（n）是矩阵阶数n的函数
    T(n) =( 2n^3) +(3n^2)+2n+1;

2.问题规模和算法的时间复杂度的关系

算法求解问题的输入量称为规模，一般用整数n表示；

一个算法的时间复杂度（Time Complexity）是指该算法的执行时间，记为T(n)，它是该算法所求解问题规模n的函数。

当问题的规模无穷大时，T(n)的数量级称为算法的渐近时间复杂度，记为T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度

这里f(n)一般是算法中最大的语句频度，一般情况下是最深层循环内的语句频度；
如：T(n) = 2n³⁺³ⁿ2+2n+1;的语句频度为T(n)=n^3
举例：

{
    int  temp；
    temp = 0;
    x=y;
    y=temp;
}

几条语句的执行频度为1，算法的执行时间是一个与问题规模无关的常数，所以算法的时间复杂度为常阶数，不管这个常数再大，它的时间复杂度都为T(n)=O(1)。
举例2

image.png

举例3

image.png

程序段的时间复杂度为T(n)=O(n^3).