数据结构 ——— 常见的时间复杂度计算例题（中篇）

目录

例题1：

例题2：

例题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)