时间复杂度如何计算？

时间复杂度怎么算？如何计算时间复杂度？
时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

步骤：

⑴ 找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

只需保留f(n)中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。

⑶ 用大Ο记号表示算法的时间性能。

将基本语句执行次数的数量级放入大Ο记号中。

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

for (i=1; i<=n; i++)

　　x++;

for (i=1; i<=n; i++)

　for (j=1; j<=n; j++)

　　x++;

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n²)，则整个算法的时间复杂度为Ο(n+n²)=Ο(n²)。

注意加法原则：T(n)=O(f(n))+O(g(n))=O(max(fn,gn))

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2^n)＜Ο(n!)<O(n^n)

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。

对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。

void aFunc(int n) {

　　for(int i = 0; i < n; i++) { // 循环次数为 n

　　printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)

　　}
}

此时时间复杂度为 O(n × 1)，即 O(n)。

对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。

void aFunc(int n) {
    for(int i = 0; i < n; i++) { // 循环次数为 n
        for(int j = 0; j < n; j++) { // 循环次数为 n
            printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
        }
    }
}                

此时时间复杂度为 O(n × n × 1)，即 O(n^2)。

对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。

void aFunc(int n) {
// 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
　　    for(int j = 0; j < n; j++) {
　　　　    printf("Hello, World!\n");
　　    }
    }
// 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
　　    printf("Hello, World!\n");
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。

void aFunc(int n) {
    if (n >= 0) {
// 第一条路径时间复杂度为 O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("输入数据大于等于零\n");
            }
        }
    } else {
// 第二条路径时间复杂度为 O(n)
        for(int j = 0; j < n; j++) {
            printf("输入数据小于零\n");
        }
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。