算法基础

算法设计的要求

我们再考虑算法的好坏时，可以认为一个特定算法“运行工作量”的大小，只依赖与问题的规模（通常用n表示）和算法本身，也就是说，这是一个问题规模的函数。

$T (n) = i \in {语句集合} \sum t_{i} \times c_{i} = i \in {语句集合} \sum c_{i}$

由于考虑所有原操作的时间不太现实且没有太多的用处，在这里直接将原操作的时间视为单位时间。

同时统计算法中所有原操作的数量也不太现实，我们直接把语句的数量视为原操作的数量

例如:

int i, sum = 0, n = 100; // 执行1次
for(i = 1; i <= n; i++) // 执行n + 1次
{
	sum = sum + i; // 执行n次
}

总共执行了 $2 n + 2$ 次。

多重循环中执行次数的判断时复杂度分析中的难点。

又例如：

int i, j, sum = 0, n = 100; // 执行1次
for(i = 1; i <= n; i++)// 执行n + 1次
{
	for(j = 1; j <= n; j++) // 执行n(n + 1)次
	{
		sum = sum + j;// 执行n * n次
	}
}

总共执行了 $1 + n + 1 + (n + 1) n + n^{2} = 2 n^{2} + 2 n + 2$ 次。

时间复杂度 $T (n)$ 还可用下面这种方式来表示

$T (n) = O (f (n))$

将 $O (f (n))$ 称为算法的渐进时间复杂度，简称为时间复杂度。

$O (f (n))$ 的定义详见离散数学，这里懒得打数学符号了。

例如：

for(int i = 1; i < n ; i++)
{
	y = y + 1;
	for(int j = 1; j <= (2 * n); j++)
	{
		x++; // 2n * n - n - 1
	}
}

时间复杂度为：

$T (n) = 2 n^{2} - n - 1 = O (n^{2})$

时间复杂度的比较：在一般情况下，指数时间复杂度都大于多项式时间复杂度

多项式时间复杂度：

$O (1) < O (l o g n) < O (n) < O (n l o g n) < O (n^{2}) < O (n^{3})$

指数时间复杂度：

$O (2^{n}) < O (n!) < O (n^{n})$

当n的取值很大的时候，指数时间算法和多项式时间算z在所需时间上的非常悬殊。因此，在设计算法的过程中，我们希望将指数时间算法化简为多项式时间的算法。

在一些情况下，算法中基本操作重复执行的次数还随着问题的输入数据集不同而不同，例如排序算法中的冒泡排序。

在冒泡排序的实际执行中，如果输入的数据本身就是有序的，那么算法的时间复杂度可以认为是0，但是在最坏的情况下，冒泡算法的时间复杂度可以达到平方阶。

空间复杂度：算法运行需要占据的存储空间大小。

$S (n) = O (f (n))$

算法的存储空间：

将上面的三部分可以分为：

如果一个算法的辅助变量和输入数据的规模无关，我们把这类算法称为就地算法。