《大话数据结构》笔记02-算法

算法

算法(Algorithm)：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

1. 输入输出
   算法可以有零个或多个输入，但至少有一个或多个输出。
2. 有穷性
   指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
3. 确定性
   算法的每一步骤都具有确定的含义，不会出现二义性。
4. 可行性
   算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

算法设计的要求

1. 正确性
   算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
2. 可读性
   算法设计的另一目的是为了便于阅读、理解和交流。
3. 健壮性
   当输入数据不合法时，算法也能做出相关处理，而不是产生异常或者莫名其妙的结果。
4. 时间效率高和存储低

算法效率的度量方法

事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。
一个程序的运行时间，主要依赖于算法的好坏和问题的输入规模(输入量的多少)。

求和算法1：

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

求和算法2：

int sum = 0, n = 100;      /* 执行1次 */
sum = (1 + n) * n/2;       /* 执行1次 */
prinf("%d", sum);          /* 执行1次 */

这个算法其实就是$n$次于1次的差距，算法的好坏显而易见。

算法时间复杂度

在进行算法分析时，语句总的执行次数 $T(n)$是关于问题规模 $n$的函数，进而分析 $T(n)$随 $n$ 的变化情况并确定 $T(n)$ 的数量级。算法的时间复杂度，也就是算法的时间度量，记作：$T(n) = O(f(n))$。它表示随问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 $f(n)$ 是问题规模 $n$ 的某个函数。
这样用大写 $O()$ 来体现算法时间复杂度的记法，称之为大O记法。

推导大O阶方法

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除于这个项相乘的常数。

得到的结果就是大O阶。

常数项

在求和算法2中，算法的运行次数函数$f(n) = 3$，根据推导大O阶方法，所以这个算法的时间复杂度为 $O(1)$。

线性阶

在求和算法1中，算法的时间复杂度为 $O(n)$。

对数阶

int count = 1;
while (count < n){
    count = count * 2;
}

有$
2^x = n
$ 得到 $
x=log_{2}n
$ 所以这个循环的时间复杂度为 $O(logn)$。

平方阶

int i, j;
for (i = o; i < n; i++){
    for (j = o; j < n; j++){
        /* ... */
    }
}

循环嵌套 时间复杂度为$O(n^2)$

如果外循环次数变为了 m，时间复杂度就变成了$O(m*n)$

int i, j;
for (i = o; i < n; i++){
    for (j = i; j < n; j++){    /* 注意j = i */
        /* ... */
    }
}

这个循环嵌套，总执行次数为：$$n + (n -1) + (n - 2) + ... + 1 = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}$$

使用推导大O阶的方法，①没有加法常数不予考虑；②只保留最高项，保留$n^2/2$；③去除这个项相乘的常数，去除$1/2$。所以时间复杂度为 $O(n^2)$。

常见的时间复杂度

常用的时间复杂度所耗费的时间从小到大依次是：
$$
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
$$
从$O(n^3)$往后，过大n都会时结果变得不现实。

最坏情况

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。