记录数据结构的学习——复杂度

时间复杂度

算法中基本操作重复执行次数称为语句频度。记为T(n)。

我们写的代码中常会出现不同的时间复杂度，时间复杂度越大，我们的程序效率便越低，例如某著名游戏联机版加载时间短则3、4分钟，长则10+分钟。这背后的原因既不是道德的沦丧，也不是人性的扭曲，而是烂代码中的一条if语句循环了19.8亿次。

在求和函数中while(–n)执行了n次，时间复杂度为O(n)

int Sum(int n)
{
	int sum = n;
	while(--n)
	{
		sum += n;
	}
	return sum;
}

优化

可优化为

int Sum(int n)
{
	int sum = n++ * n / 2;
	return sum;
}

此时由于只执行了一次( n++ * n / 2)， 所以时间复杂度为O(1)。

增长率

当输入规模增加时，时间复杂度增加的速度

由上表我们不能否认一个结论，那就是好的时间复杂度的算法可以提高很多效率。

空间复杂度

完成算法所需空间的度量。//额外空间

在此求和函数中

int Sum(int n)
{
	int sum = n;
	if (--n)
	{
		sum += Sum(n);
	}
	return sum;
}

虽只用了一个变量sum，但进行了n次递归调用，所以空间复杂度为O(n)。

化简

int Sum(int n)
{
	int sum = n++ * n / 2;
	return sum;
}

在这个求和函数中，只用了一个变量sum，所以空间复杂度为O(1)。

O(n)的化简

1、若T(n)在O(g(n))中，g(n)在O(h(n))中，则T(n)在O(n)中。
2、对于任意的正常数k，若T(n)在O(k * g(n))中， 则T(n)在O(g(n))中。//系数不影响时间复杂度
3、若T1(n)在O(g1(n))中，T2(n)在O(g2(n))中，则T1(n) + T2(n)在O(Max(g1(n), g2(n)))中。//加法中考虑增加速度最快的一条曲线。
4、若T1(n)在O(g1(n))中，T2(n)在O(g2(n))中，则T1(n) * T2(n)在O(g1(n) * g2(n))中。//乘法中考虑嵌套的代码，

例如 T(n) = 3n ^ 2 + 4n + 5。
由2知 令 k = 1 , T(n) 在O(3n ^ 2 + 4n + 5)中，可看做T(n + 0 + 0)在O(3n ^ 2 + 4n + 5)。
由3知 T(n) 在O(Max(3n ^ 2 , 4n, 5))中，显然当n较大时，Max(3n ^ 2 , 4n, 5)为3n ^ 2。则T(n)在O(3n^2)中。
由2知 3n^ 2 在 O(n ^ 2) 中。
由1知 T(n) 在 O(n ^ 2) 中。