常见的五种时间复杂度：
- O(1)：常数复杂度，最快的算法
取数组第1000000个元素
字典和集合的存取都是O(1)
数组的存取是O(1)
- O(logN)：对数复杂度
假设有一个有序数组，以二分法查找
- O(n)：线性复杂度
假设有一个数组，以遍历的方式在其中查找元素
- O(nlogN)：求两个数组的交集，其中一个是有序数组
A数组每一个元素都要在B数组中进行查找操作
每次查找如果使用二分法则复杂度是logN。
- O(n^2)：平方复杂度
求两个无序数组的交集
- 对于一个循环，假设循环体的时间复杂度为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++){ //循环次数为n
for (int j = 0; j < n; j++){ //循环次数为n
printf("Hello world!\n"); //循环体时间复杂度为O(1)
}
}
//第二部分时间复杂度为O(n)
for (int j = 0; j<n; j++){ //循环次数为n
printf("Hello world!\n"); //循环体时间复杂度为O(1)
}
}
此时时间复杂度为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)。
时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。
