时间复杂度

2019-05-22  本文已影响0人  FRAJ

常见的五种时间复杂度:

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

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

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

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

求两个无序数组的交集


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

  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(n*n*1),即O(n^2)。

  1. 对于顺序执行的语句或者算法,总的时间复杂度等于其中最大的时间复杂度。
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)。

  1. 对于条件判断语句,总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。
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)。

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

上一篇 下一篇

猜你喜欢

热点阅读