数据结构 ——— 常见的时间复杂度计算例题（中篇）
目录
例题1：
代码演示：
void BubbleSort(int* a, int n)
{
// 断言
assert(a);
// 循环1
for (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;
// 循环1
while (left <= right)
{
int mid = (left + right) / 2;
if (a[mid] < x)
left = mid + 1;
else if (a[mid] > x)
right = mid - 1;
else
return 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)
原文地址：https://blog.csdn.net/weixin_55341642/article/details/142411959
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！