时间复杂度

海棠蚀omo

发布于 2026-01-12 16:42:31

780

1.1时间复杂度概念

其实就是一个函数式T(n)，并非具体的运行时间，就算该算法的时间复杂度。

void func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			count++;
		}
	}

	for (int k = 0; k < 2 * N; k++)
	{
		count++;
	}

	int M = 0;
	while (M--)
	{
		count++;
	}

	printf("%d\n", count);
}

就如这个例子而言，func1的基本执行次数：T(N)=N^2+2*N+M，在计算时间复杂度的时候，计算的并不是具体的执行次数，而是大概执行次数，其实就是找对结果影响最大的一项，而找这个就要用到大O的渐进表示法。

1.2大O的渐进表示法

计算时间复杂度就是利用大O的渐进表示法。

1.3常见例子

例一：

void func2(int N)
{
	int count = 0;
	
	for (int k = 0; k < 2 * N; k++)
	{
		count++;
	}

	int M = 0;
	while (M--)
	{
		count++;
	}

	printf("%d\n", count);
}

时间复杂度：O(N)

这个例子的执行次数：T(N)=2*N+M，显而易见2*N是对结果影响最大的一项，并且根据渐近法的第二条可得本例的时间复杂度。

例二：

void func3(int N,int M)
{
	int count = 0;
	
	for (int i = 0; i < N; i++)
	{
		count++;
	}

	for (int j = 0; j < M; j++)
	{
		count++;
	}
	

	printf("%d\n", count);
}

时间复杂度：O(M+N)

这个例子的执行次数：T(N)=N+M，但是因为N和M的大小并不知道，故时间复杂度只能写成O(M+N)

例三：

void func4()
{
	int count = 0;
	for (int i = 0; i < 10; i++)
	{
		count++;
	}
}

时间复杂度：O(1)

这个例子的执行次数：T(N)=10，这个程序循环了10次，是一个具体的数字，故根据渐近法的第三条可得时间复杂度

例四：

void func5(int* arr,int n)
{
	assert(arr);
	for (int end = n; end > 0; end--)\
	{
		int exchange = 0;
		for (int i = 1; i < end; i++)
		{
			if (arr[i - 1] < arr[i])
			{
				Swap(&arr[i - 1], &arr[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}

}

时间复杂度：O(N^2)

这个例子是冒泡排序，计算它的执行次数可以把每次循环的执行的次数写下来，写下来，比如第一次：n-1，第二次：n-2......到最后一次就是1，很明显，这就是一个等差数列，而总的执行次数就是等差数列求和，之后根据渐近法就能找出时间复杂度。

1.4最好，最差，平均情况

例如：在一个长度为N的字符串中找一个字符

最好情况：O(1)

最坏情况：O(N)

平均情况：O(N)

一般情况下算法的时间复杂度都取最坏情况。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-17，如有侵权请联系 cloudcommunity@tencent.com 删除

int