数据结构——时间复杂度和空间复杂度

目录

时间复杂度

什么是时间复杂度

常见时间复杂度类型

如何计算时间复杂度

空间复杂度

什么是空间复杂度

常见的空间复杂度类型

如何计算空间复杂度

---

时间复杂度和空间复杂度是评估算法性能的两个重要指标。

时间复杂度

什么是时间复杂度

时间复杂度描述了算法执行所需时间随输入规模增长的变化趋势。它通常用大O表示法来描述，表示算法在最坏情况下的时间性能。

常见时间复杂度类型

• 常数时间：O(1)。算法执行时间不随输入规模的变化而变化。
• 线性时间：O(n)。算法执行时间与输入规模成正比。
• 平方时间：O(n^2)。算法执行时间与输入规模的平方成正比，通常见于嵌套循环。
• 对数时间：O(logn)。算法执行时间随输入规模的增长而缓慢增加，常见于分治和二分查找算法。
• 线性对数时间：O(nlogn)。算法执行时间是输入规模与对数的乘积，常见于快速排序或归并排序。
• 指数时间：O(2^n)。算法执行时间随输入规模指数增长，常见于暴力搜索。

在大O表示法中，logn一般指的是以2为底的对数，因为绝大部分都只用考虑二分的情况，以其他数为底的情况很少出现。

如何计算时间复杂度

exp.1

//Func1的时间复杂度为O(N)
void Func1(int N)
{
	int i = 0;
	int count = 0;
	for (i = 0; i < N; i++)
	{
		++count;
	}
	int m = 10;
	while (m)
	{
		--m;
	}
	printf("%d\n",count);
}

该函数的运行时间主要跟输入的N的大小有关，故为O(n)的时间。

至于说下面的执行的m次循环，我们是不用理会的，因为在输入的N很大的情况，m次循环可以被忽略掉。我们算时间复杂度都是关注主要最主要的部分，比如说O(n^2 + 2n)， 那么时间复杂度是O(n^2)。

exp.2

//Func2的时间复杂度为O(N)
void Func2(int N)
{
	int count = 0;
	int i = 0;
	for (i = 0; i < N; i++)
	{
		++count;
	}
	for (i = 0; i < N; i++)
	{
		++count;
	}
	printf("%d\n",count);
}

这里咋一看时间复杂度是O(2n)，但其实时间复杂度还是O (n)。

计算机运行的时间是非常快的，所以即使n非常大，n的常系数对于整个函数的运行时间是微乎其微的。

所以算时间复杂度也不用算n的常系数。

exp.3

//Func3的时间复杂度为O(1)
void Func3()
{
	int count = 0;
	int i = 0;
	for (i = 0; i < 100; i++)
	{
		++count;
	}
	printf("%d\n",count);
}
 

时间复杂度为O(1)，因为是常数次运行。

exp.4

// BubbleSort的时间复杂度为O(N^2)
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

外层循环执行n次，内层循环执行n-1次、n-2次...等，等差乘等比，最会算出来会有n^2，所以时间复杂度是O(n^2)。

exp.5

// BinarySearch的时间复杂度O(logN)
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		//使用右移操作符相当于除以2
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

二分查找的时间复杂度是O(logn)，就是对n取以二为底的对数。

exp.6

// 阶乘递归Fac的时间复杂度为O(N)
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
 
	return Fac(N - 1) * N;
}

递归的次数同样也算进时间复杂度，这里递归了n次，所以时间复杂度是O(n)。

这里的空间复杂度也是O(n)，因为递归调用函数会在栈上多开n块额外的空间。

exp.7

// 斐波那契递归Fib的时间复杂度为O(2^N)
long long Fib(size_t N)
{
	if (N < 3)
		return 1;
 
	return Fib(N - 1) + Fib(N - 2);
}

以这种方法算斐波那契数列的递归调用次数，有点类似算完全二叉树的节点个数。

所以时间复杂度是O(2^n)。

总结

时间复杂度只需大概想想执行次数n的表达式，取次数最大的那项，也不用理会n的常系数。

如果涉及递归，要想想递归函数的执行次数。

空间复杂度

什么是空间复杂度

空间复杂度描述了算法执行过程中所需的额外存储空间量，也用大O表示法来描述。

常见的空间复杂度类型

• 常数空间：O(1)。算法使用固定数量的额外空间，与输入规模无关。
• 线性空间：O(n)。算法使用的额外空间与输入规模成正比。
• 平方空间：O(n^2)。算法使用的额外空间与输入规模的平方成正比。
• 对数空间：O(logn)。算法使用的额外空间随输入规模的增长而缓慢增加。
• 线性对数空间：O(nlogn)。算法使用的额外空间是输入规模与对数的乘积。

如何计算空间复杂度

exp.1

//sum的空间复杂度是O(1)
int sum(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += i;
    }
    return sum;
}

sum只额外开辟变量sum，额外开辟的空间跟输入的n无关，所以空间复杂度是O(1)

exp.2

//Func的空间复杂度是O(n)
void Func(int n)
{
    int* arr = (int*)malloc(sizeof(int) * n);
    //....
 
}

Func使用的空间复杂度是O(n)，因为额外开辟的空间与n成正比。

总结

计算空间复杂度只需看使用的额外存储空间与输入数据规模大小的关系，比如，跟规模无关就是O(1)，跟规模成正比就是O(n)，其他O(n^2)等同理。

---

拜拜，下期再见