北京公司网站设计价格,抽奖的网站怎么做的,廊坊关键词排名首页,厦门网站建设手机目录
1.二分法的时间复杂度
解:
2.求阶乘的时间复杂度
解:
3.递归实现斐波那契数,求时间复杂度
解:
4.时间复杂度的排名 备注:有关时间复杂度的讲解参见80.【C语言】数据结构之时间复杂度
1.二分法的时间复杂度
(代码来自E7.【C语言】练习#xff1a;在一个有序数组中…目录
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;
}
解:
最好:数组的中间元素恰为需要查找的元素,时间复杂度为
最坏:
第1次在N/2处查找第2次在N/4处查找第3次在N/8处查找............第x次在处查找
当缩放到一个值时,即,则
时间复杂度为,也可以写为(此写法仅限于以2为底的),部分教材写为(不推荐)
对比最好和最坏的情况 再对比遍历查找的时间复杂度
自变量越大,两者差距越明显
取最坏的情况作为时间复杂度
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);
}
解:
时间复杂度为
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 afbi(n);printf(%d\n, a);
}
解:
此代码为求第n个斐波那契数 时间复杂度为
(补一个树状图)
图,显然执行程序的话会大量占用CPU的资源
4.时间复杂度的排名
