目录
例题1:
例题2:
例题1:
代码演示:
void BubbleSort(int* a, int n)
{// 断言assert(a);// 循环1for (size_t end = n; end > 0; end--){int flag = 0;// 循环2(循环1的内部循环)for (size_t i = 1; i < end; i++){if (a[i - 1] > a[i]){// 交换Swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0)break;}
}
问:计算 BubbleSort 函数的时间复杂度?
代码解析:
例题1 代码的意思是:对整型数组 a 排序,排成升序,且根据 flag 变量判断当前的整型数组 a 是否为升序,是的话就直接跳出循环(也就是冒泡排序)
像是 例题1 这种的代码,不会固定执行 N 次,而是要分情况看待,且在实际中一般情况关注的是算法的最坏运行情况,所以以最坏的情况举例(也就是当前整型数组 a 为降序的情况时):
当整型数组 a 为降序时,第一个元素就要交换 N-1 次才能到最终该停留的位置,第二个元素就要交换 N-2 次才能到最终该停留的位置…………,以此类推,可以发现各个元素交换次数的总和加起来是一个等差数列,由此得出时间复杂度函数式:
时间复杂度函数式:F(N) = N*(N-1)/2 = (N^2-N)/2
再根据时间复杂度函数式和大O的渐进表示法的规则推导出大O的渐进表示法:只保留最高阶项(除去 F(N) 中的 N) ;如果最高阶项存在且不是1,则去除与这个项目相乘的常数(除去 F(N) 中的2 ),得出大O的渐进表示法
大O渐进表示法:O(N^2)
例题2:
代码演示:
int BinarySearch(int* a, int n, int x)
{assert(a);int left = 0;int right = n - 1;// 循环1while (left <= right){int mid = (left + right) / 2;if (a[mid] < x)left = mid + 1;else if (a[mid] > x)right = mid - 1;elsereturn mid;}return -1;
}
问:计算 BinarySearch 函数的时间复杂度?
代码解析:
例题2 代码的意思是:二分查找,找到了返回 x 元素的下标,没找到返回 -1(前提:整型数组 a 是有序的)
例题2 同样要用最坏的情况看待(也就是 left 和 right 相等的情况下才找到 x ,或者没有找到 x):
整型数组 a 的长度是 N ,每循环一次,N 就缩小一半…………,也就是 N/2/2/……/2 = 1(当 left 等于 right 的时候就停止),假设循环了 x 次,那么 N/2/2/……/2 = 1 这个式子就被替换为 N/(2^x) = 1 (等式左右两边乘上 2^x )得:N = 2^x ,再 x = logN,所以得出时间复杂度函数式:
时间复杂度函数式:F(N) = logN(注意:log是以2为底)
再由时间复杂度函数式直接得出大O的渐进表示法:
大O渐进表示法:O(logN)