时间复杂度

常见的五种时间复杂度：

• O(1)：常数复杂度，最快的算法

取数组第1000000个元素
字典和集合的存取都是O(1)
数组的存取是O(1)

• O(logN)：对数复杂度

假设有一个有序数组，以二分法查找

• O(n)：线性复杂度

假设有一个数组，以遍历的方式在其中查找元素

• O(nlogN)：求两个数组的交集，其中一个是有序数组

A数组每一个元素都要在B数组中进行查找操作
每次查找如果使用二分法则复杂度是logN。

• O(n^2)：平方复杂度

求两个无序数组的交集

---

1. 对于一个循环，假设循环体的时间复杂度为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)。

2. 对于多个循环，假设循环体的时间复杂度为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)。

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

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)。

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

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)。

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