时间复杂度计算-例题集合

)

一、常数阶

// 常数阶  int result = 100; //运行程序只执行一次  result ++ ; //执行一次 System.out.println ("Hello!"+result); //执行一次  

上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，每次运行程序每条语句执行一次，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。

例：

void fun4(int N) { 
     int count = 0; for (int k = 0; k < 100; k++) { 
     ++count; } printf("%d\n", count); } 

fun3的基本操作的执行了100次，通过推导大O阶方法知道，时间复杂度为O（1）。

二、线性阶

//线性阶 for(int i=0;i<n;i++){ 
     System.out.println(result[i]); //执行一次 } 

三、对数阶

// 对数阶 int result=1; while(result<n){ 
     result=result*2; //时间复杂度为O(1) } 

可以看出上面的代码， result=result*2; 随着result每次乘以2后，都会越来越接近n，当result大于等于n时就会退出循环（限制条件）。

如果循环的次数为T，所以2^T=n于是T=log₂n，因此得出这个算法的时间复杂度为O(logn)。

例题：
二分查找

//二分查找法 int BinarySearch(int* a, int n, int x) { 
     assert(a); int begin = 0; int end = n - 1; while (begin < end) { 
     int mid = ((end - begin) >> 1) + begin; //计算end与begin的中间值，右移1位相当于除以2 if (a[mid] < x) { 
    begin = mid - 1;} else if(a[mid]>x){ 
    end = mid;} else { 
    return mid;} } return -1; } 

对于BinarySearch函数来说，它存在

最好情况:执行1次 最坏情况:约执行logN次，这里的logN是以2为底，以N为对数。 

这里我们考虑最坏情况，时间复杂度为：O(logN)。分析如下：

第一次查找：在长度为N的数组中查找值，取中间值进行比较 第二次查找：在长度为N/2的数组中查找值，取中间值进行比较 第三次查找：在长度为N/(2^2)的数组中查找值，取中间值进行比较 … 第logN次查找：在长度为N/(2^logN)的数组中查找值，即在长度为1的数组中查找，无论是否找到均跳出循环，结束查找。 

四、平方阶

4.1

 // 平方阶 for(int i=0;i<n;i++){ 
     for(int j=0;j<n;i++){ 
     System.out.println(result[i][j]); //执行一次  } } 

这是一个循环嵌套的语句，很明显内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，又经过了外层循环n次，那么这段算法的时间复杂度则为O(n²)。

4.2

void fun(int n){ 
     int i,j,x=0; for(i=1;i<n;i++){ 
     for(j=n;j>=i+1;j--){ 
     x++; } } } 

4.3

void fun(int n){ 
     int i=0; while(i*i*i<=n){ 
     i++; } } 

4.44.5
4.6冒泡排序

void Swap(int* a, int* b) { 
     int c = *a; *a = *b; *b = c; } //冒泡排序 --从小到大 void BubbleSort(int* a, int n) { 
     assert(a);//异常处理 for (int end = n; end > 0; --end) { 
     int exchange = 0; for (int i = 1; i < end; ++i) { 
     if (a[i - 1] > a[i]) { 
     //两个数据进行比较，前面一个数据大于后一个数据 Swap(&a[i - 1], &a[i]); exchange = 1; } } //如果遍历整个数组，发现没有数据进行交换，即每个元素均小于等于后一个元素 //则无须在进行排序，直接结束循环即可 if (exchange == 0) break; } } 

对于BubbleSort函数来说，它存在

最好情况:数组为顺序，执行N次 最坏情况:数组为逆序，执行N*(N+1)/2次 

五、多个复杂度组合：顺序结构

// 多个复杂度组合 for(int i=0;i<n;i++){ 
     for(int j=0;j<n;i++){ 
     System.out.println(result[i][j]); //执行一次  } } for(int i=0;i<n;i++){ 
     System.out.println(result[i]); //执行一次  } 

对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。

六、多个复杂度组合：选择结构

// 多个复杂度组合 if(flag){ 
     for(int i=0;i<n;i++){ 
     for(int j=0;j<n;i++){ 
     System.out.println(result[i][j]); //执行一次  } } }else{ 
     for(int i=0;i<n;i++){ 
     System.out.println(result[i]); //执行一次  } } 

对于条件判断语句，总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。所以对于以上的代码，时间复杂度为O(n²)。

七、多个复杂结构：嵌套结构

void fun(int n){ 
     int i,k; for(i=1;i<=n;i++){ 
     for(j=1;j<=n;j++){ 
     k=1; while(k<=n){ 
     k = 5*k; } } } } 

八、递归

//求阶乘 long long Factorial(int N) { 
     return N < 2 ? N : N * Factorial(N - 1) ; } 

例

//斐波那契函数 long long Fibonacci(int N) { 
     return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2); }