时间复杂度怎么算？如何计算时间复杂度？时间复杂度
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需保留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)。
时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。
版权声明：本文为wonker原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。