树状菜单网站,网站打开不对,互助县wap网站建设公司,建筑设计防火规范定义#xff1a;
在计算机科学中#xff0c;时间复杂性#xff0c;又称时间复杂度#xff0c;算法的时间复杂度是一个函数#xff0c;它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述#xff0c;不包括这个函数的低…定义
在计算机科学中时间复杂性又称时间复杂度算法的时间复杂度是一个函数它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述不包括这个函数的低阶项和首项系数。使用这种方式时时间复杂度可被称为是渐近的亦即考察输入值大小趋近无穷时的情况。
将数字从 1~100 进行排序不同的人用不同的方法写出的程序都会有所偏差这就需要我们对编写这个算法有一定的预期了解这部分算法的运行效果如果运行效果不适用就没必要使用这个算法。我们不需要知道某种算法具体的执行时间而是用大O表示法表示时间的概念也就是时间复杂度。
大O表示法一般就是来表示某个函数的时间复杂度所以 O 代替了函数名字括号里面的代数表示 函数参数。
O(1)
每天去上班只需要和老板一个人打招呼不管招呼内容是什么这件事情只需要做一次每次花费的时间几乎是相等的我们就可以用 O(1) 来表示这所消耗的时间。
int msg(const char * msg) {printf(%s \n, msg); // 需要执行一次
}这里不管输入的字符串有多大都是常量对于程序而言就只需要执行一次把每次执行消耗的时间约等于相等那么用x,y轴的形式来表示就会是一条直线我们直接O(1)来表示这样的常量时间。
O(n):
每天去上班需要和公司所有人都打招呼就需要你每天和公司这n个人逐个问候虽然与每个人打招呼时间相同但是要进行n多次因此我们就用O(n)来表示。
int msg(int n) {for (int i 0; i n; i) { // 需要执行 (n 1) 次printf(Hello!\n); // 需要执行 n 次}return 0; // 需要执行 1 次
}这个函数需要遍历数组里面所有元素因为数组里每个元素都需要遍历一次所以数组如果有非常多元素就需要执行多次也就可以用 O(n) 来表示。因为很明显是一种线性的时间如果n越大也就是这个数组的元素越多。消耗的时间也就是越多的。
O(n²):
公司业务扩招现在有多个部门你需要每天上班先给部门A所有人逐个打招呼然后再给部门B里面所有人逐个打招呼剩下所有部门都是这样打招呼我们就可以用O(n^²)来表示这所耗费的时间因为你不止要遍历每个部门还要遍历每个部门的人。
void msg(int numberofDepartments, int numberOfPeople) {for (int i 0; i numberofDepartments; i) { // 循环次数为 nfor (int j 0; j numberOfPeople; j) { // 循环次数为 nprintf(Hello!\n); // 循环体时间复杂度为 O(1)}}
}也就是嵌套循环这里一共有多少个部门 numberofDepartments,部门中有多少人 numberOfPeople。比方说有4个部门每个部门有4个人那么这里输出打招呼的信息就是 16 次也就是 4 ² 16 ,所以用 O(n²) 来表示. O(log n)
2¹ 2
2³ 8
2⁵ 32
2¹⁰ 1024如果用 log 的形式写:
log₂2 1
log₂8 3
log₂32 5
log₂1024 10
这里的 2,8,32,1024 就是 n,这个n即使变得很大结果并没有等比例增大就是结果的增速缓慢。每次对半分的话越到后面需要消耗的时间相对就越少。这里 O(log n) 并没有把底数 ₂ 写出来
#include stdio.h
int binary_search(int *arr,int p,int q,int ele) {int mid 0; if (p q) {return -1;} mid p (q - p) / 2; if (ele arr[mid]) {return mid;} if (ele arr[mid]) { return binary_search(arr, p, mid - 1, ele);}else { return binary_search(arr, mid 1, q, ele);}
}int main()
{int arr[10] { 10,14,19,26,27,31,33,35,42,44 };printf(%d, binary_search(arr, 0, 9, 31));return 0;
} 这是一个二分法查找
