时间复杂度
方法： 1、按效率从高到低排列：
2、取最耗时的部分
4个便利的法则：
- 对于一个循环，假设循环体的时间复杂度为 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)，各个循环的循环次数分别是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(1×n×n)，即O（n²）- 对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。
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");
}
}
时间复杂度为：O（n²）- 对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径 的时间复杂度。
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");
}
}
}
时间复杂度为：O（n²）举个栗子~ 例：
代码语言：javascript复制//代码 1
int a = 1;
while (a <= n) {
a = a * 2;
}时间复杂度为：O(logn)
代码语言：javascript复制//代码 2
for (int i = 0; i < n; i ) {
for (int j = 0; j < n; j ) {
for (int k = 0; k < n; k ) {
a ;
}
}
}//O(n³)
int m = 1;
for (int i = 1; i <= n; i ) {
m *= i;
}//O(n!)
for (int i = 0; i < m; i ) {
b ;
}//O(n!)时间复杂度为：O(n!)
代码语言：javascript复制//代码3
void aFunc(int n) {
for (int i = 2; i < n; i ) {
i *= 2;
printf("%in", i);
}}
//假设循环次数为 t，则循环条件满足 2^t < n。
//可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。时间复杂度为：O（logn）
代码语言：javascript复制//代码4
long aFunc(int n) {
if (n <= 1) {
return 1;// 需要执行 1 次
}
else {
return aFunc(n - 1) aFunc(n - 2);
}//T（n-1） T(n-2) 1 —— 这里的1表示加法执行一次
}
//T(n) = T(n - 1) T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。
//该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。时间复杂度为：O（2^n）
