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

目录

前言

例题1：

例题2：

例题3：

例题4：

前言

在上一章讲解了时间复杂度的概念，以及用 大O的渐进表示法 表示 时间复杂度

数据结构 ——— 算法的时间复杂度-CSDN博客

接下来利用C语言代码的例题，更深一步的掌握用 大O的渐进表示法 表示 代码的时间复杂度

例题1：

代码演示：

void Func1(int N)
{
	int count = 0;

    // 循环1
	for (int k = 0; k < 2 * N; k++)
	{
		count++;
	}
	
	// 循环2
    int M = 10;
	while (M--)
	{
		count = count + 1;
	}
}

问：计算 Func1 函数的时间复杂度？

代码解析：

循环1 执行了 2*N 次，循环2 执行了 10 次 

时间复杂度函数式：F(N) =  2*N + 10

根据大O的渐进表示法的规则：只保留最高阶项（除去 F(N) 中的10） ；如果最高阶项存在且不是1，则去除与这个项目相乘的常数（除去 F(N) 中的2），得出大O的渐进表示法

大O渐进表示法：O(N)

例题2：

代码演示：

void Func2(int N, int M)
{
	int count = 0;

	// 循环1
	for (int k = 0; k < N; k++)
	{
		count++;
	}

	// 循环2
	for (int k = 0; k < M; k++)
	{
		count++;
	}
}

问：计算 Func2 函数的时间复杂度？

代码解析：

循环1 执行了 N 次，循环2 执行了 M 次

时间复杂度函数式：F(N) =  N + M

根据大O的渐进表示法的规则：N 和 M 都是平阶，且不是常数，所以都要保留下来，得出大O的渐进表示法

大O的渐进表示法：O(N + M)

例题3：

代码演示：

void Func3(int N)
{
	int count = 0;

	// 循环1
	for (int k = 0; k < 100; k++)
	{
		count++;
	}
}

问：计算 Func3 函数的时间复杂度？

代码解析：

循环1 执行了 100 次

时间复杂度函数式：F(N) = 100

根据大O的渐进表示法的规则：用常数1取代运行时间中的所有加法常数（ F(N) 中的 100 取代为1），得出大O的渐进表示法

大O的渐进表示法：O(1)

注意：O(1) 并不是代表代码只执行了 1 次，而是代表代码执行了常数次

例题4：

代码演示：

const char* Find_Str_Element(const char* str, int character)
{
	while (*str != '\0')
	{
		if (*str == character)
			return str;
		else
			str++;
	}

    return NULL;
}

问：计算 Find_Str_Element 函数的时间复杂度？

代码解析：

例题4 代码的意思是：在 str 字符串中找出和 character 相同的元素，如果找到了就返回 character 位置的指针，如果 str 字符串遍历完了都没有找到就返回 NULL

但是 例题4 代码的运行次数并不是像 例题1、2 一样，固定执行 N 次 或者 N + M 次，而是要分情况看待：

最好情况：character 元素是 str 字符串首元素，程序执行 1 次 

中间情况：character 元素是 str 字符串中间元素，程序执行 N/2 次

最坏情况：character 元素是 str 字符串尾元素 或者 str 中没有 character ，程序执行 N 次

注意：在实际中一般情况关注的是算法的最坏运行情况（底线思维，做最坏的打算）

所以 str 字符串查找 character 元素的时间复杂度为：O(N)