网站建设公司哪个靠谱_品牌宣传方式_百度营销中心_商丘seo外包

1.二分法的时间复杂度

解:

2.求阶乘的时间复杂度

解:

3.递归实现斐波那契数,求时间复杂度

解:

4.时间复杂度的排名

备注:有关时间复杂度的讲解参见80.【C语言】数据结构之时间复杂度

1.二分法的时间复杂度

(代码来自E7.【C语言】练习：在一个有序数组中查找具体的某个数字n（二分查找）)

a[]是有序数组

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
int main()
{int a[] = { 1,4,5,7,9,10,20,45,46,68,79,81,90,100,104,111,129,137,139,140,157,163,172,199,200 };//数组自己设定int search = 0;int length = sizeof(a) / sizeof(a[0]);//数组的元素个数int left = 0;int right = length - 1;//left和right为查找数组范围的下标，即从a[left]~a[right]间查找int middle = 0;//left和right之间的中值int sum = 1;//统计查找次数for (int i = 0; i < length; i++)printf("%d ", a[i]);//打印数组printf("\n一共%d个数\n", length);printf("查找:");scanf("%d", &search);printf("在a[%d]和a[%d]间查找\n", left, right);while (left <= right){int middle = (left + right) / 2;if (a[middle] < search){left = middle + 1;printf("在a[%d]和a[%d]间查找\n", left, right);sum += 1;}else if (a[middle] > search){right = middle - 1;printf("在a[%d]和a[%d]间查找\n", left, right);sum += 1;}else{if (left > right){printf("找不到");break;}if (a[middle + 1] == search)printf("找到了，是a[%d],查找了%d次", middle + 1, sum);else if (a[middle] == search)printf("找到了，是a[%d],查找了%d次", middle, sum);elseprintf("找到了，是a[%d],查找了%d次", middle + 1, sum);break;}if (left > right)printf("找不到");}return 0;
}

解:

最好:数组的中间元素恰为需要查找的元素,时间复杂度为 $O(1)$

最坏:

第1次	在N/2处查找
第2次	在N/4处查找
第3次	在N/8处查找
......	......
第x次	在 $N/(2^x)$ 处查找

当缩放到一个值时,即 $2/(2^x)=1$ ,则 $x=O(\log_2 N)$

时间复杂度为 $O(\log_2 N)$ ,也可以写为 $O(logN)$ (此写法仅限于以2为底的),部分教材写为 $O(lgN)$ (不推荐)

对比最好和最坏的情况

再对比遍历查找的时间复杂度 $O(N)$

自变量越大,两者差距越明显

取最坏的情况 $O(logN)$ 作为时间复杂度

2.求阶乘的时间复杂度

(代码来自35.【C语言】详解函数递归)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
long long fact(size_t n)
{if (0 == n)//限制条件return 1;elsereturn n * fact(n - 1);
}
int main()
{size_t n = 0;scanf("%zd", &n);long long a = fact(n);printf("%lld\n", a);
}

解:

时间复杂度为 $O(N)$

3.递归实现斐波那契数,求时间复杂度

(代码来自35.【C语言】详解函数递归)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int fbi(int n)
{if (1 == n || 2 == n){return 1;}else{return fbi(n - 1) + fbi(n - 2);}
}int main()
{int n = 0;scanf("%d", &n);int a=fbi(n);printf("%d\n", a);
}