算法与数据结构之绪论

算法

什么是算法？

听到”算法（Algorithm）”这个词，大部分人都觉得好像艰深晦涩。的确，这不是一个常常听到的词。事实上，在数学、计算机等理工科领域，所谓的算法，指的就是“对特定问题解决的步骤”。而这里的特定问题，通常有：

对信息进行排序
搜索目标信息

等不同问题。
此外，如果说“算法是解决问题的步骤”，那么撇开计算机的数据处理不论，现实生活中也有很多问题的解决方法蕴含了算法的思想。这其中的代表就是菜谱。

算法和菜谱

算法的作用及意义？

算法是人类智慧的结晶，寻求更加优雅的解法。

在程序中应用算法。自计算机面世，在利用计算机解决各种各样的“问题”时，无数解法、步骤被人们提出来。“是不是更好地复用”、“是不是可以更高效”、“是不是可以花费更少的空间代价”等，很多研究者会从这些方面对现存的算法进行改善。而历经时间的洗练，那些优雅的算法正在被应用到各种计算机程序中去。
算法和菜谱

算法两个必要条件

“准确性”和“可停止性”

准确性：对相应的问题，算法必须能够得出正确的结果。证明算法准确性的其中一个方法是，“对于算法中的任意一个步骤，输入当前步骤满足条件的值，看看是否能得到当前步骤产生的准确的结果，以此细分并判断。”这种方法叫断言（Assertion） 。
可停止性：算法必须是最终可停止的。算法的可停止性也就是“保证无论什么样的输入，也一定可以在有限时间内正确的停止”。

算法和菜谱

算法分析

算法分析的目标是根据运行的时间及其他的一些因素（如内存、开发者的工作量等）来比较算法（或解决方案）的优劣。

为了比较算法，首先定义几个客观评价指标：

执行时间:它不是一个好的指标，因为执行时间与特定的计算机有关。
执行的语句数：它也不是一个很好的评价指标，因为执行的语句数和编程语言有关，也与程序猿个人的编程风格有关。
理想指标：假设用一个函数$f(n)$来表示一个算法的运行时间，该函数的输入参数就是问题的规模$n$。然后比较这些不同函数对应的运行时间。这种比较与机器时间、编程风格等无关。

常用的增长率

时间复杂度	名称	实例
1	常数	在链表的前端增加一个元素
$logn$	对数	在有序数组中查找一个元素
$n$	线性	在无序数组中查找一个元素
$nlogn$	线性对数	通过分治，归并排序n个元素
$n^2$	平方	求图中两个顶点之间的最短距离
$n^3$	立方	矩阵乘法
$2^n$	指数	汉诺塔问题的求解

增长率

分析的类型

算法分析有三种类型：

最坏情况
- 定义算法最长运行时间的输入。
- 这种输入使算法运行最慢。
最好情况
- 定义算法最短运行时间的输入。
- 这种输入使算法运行最快。
平均情况（期望）
- 提供算法运行时间的预测值。

对于一个给定的算法，可以用表达式来描述算法的最好、最坏和平均情况。例如，函数$f(n)$代表给定的算法。
$f(n)=n^2+500$,对应最坏情况
$f(n)=n+1000n+500$,对应最好情况

渐近表示

有了描述算法的最好、最坏和平均情况的三种表达式后，对每种表达式还需要确定算法的上界和下界。

大$O$表示法：给出了算法函数的严格上限。一般来说，它可以表示为$f(n)=O(g(n))$,这表示当输入规模$n$很大时，$f(n)$的上界时$g(n)$。例如，对于给定的算法$f(n)=n^4+100^2+10n+50$，那么$g(n)=n^4$。这意味着问题规模$n$的增大，$g(n)$决定了$f(n)$的最大增长率。
$\Omega$表示法：给出算法函数的严格的下界。它可以表示为$f(n)=\Omega(g(n))$。也就是说，当输入规模$n$增大时，$f(n)$的严格下界是$g(n)$。例如，$f(n)=1oon^2+10n+50$,$g(n)=\Omega(n^2)$
$\Theta$表示法：给定算法的时间增长率的上界和下界是否相同。算法的平均运行时间总是介于上界和下界之间。如果上界$(O)$和下界$\Omega(n)$给出的结果是一样的，那么$\Theta$也会得出相同的增长率；如果不同，需要分析所有可能的时间复杂度，然后得出平均情况下的结论。

重要说明

在分析最好、最坏和平均时间，试图给出算法的上界$(O)$、下界$(\Omega)$和平均时间$(\Theta)$。对于给定算法，得到它的上界$(O)$、下界$(\Omega)$和平均时间$(\Theta)$可能并不容易。
通常对于一个算法我们最关心的是算法时间复杂度的上界$(O)$，因为求下界$(\Omega)$没有实际意义。

渐近分布举例

有些通用的规则帮助我们确定一个算法的运行时间。

循环：一个循环体的运行时间最多为——循环体内语句的运行时间（包括循环条件判断）与迭代次数的乘积。

// 循环执行n次
for (i=1;i<=n ;i++ ) {
    m +=2;//时间常数c
}

总时间$=c×n=cn=O(n)$

嵌套循环：从内到外进行分析。总的运行时间是所有循环规模的乘积。

// 外层循环执行n次
for (i=1;i<=n ;i++ ) {
    // 内层循环执行n次
    for (j=1;j<=n ;j++ ) {
        k +=2;//时间常数
    }
}

总时间=$c×n×n=cn^2=O(n^2)$

顺序执行语句：每条语句的运行时间相加。

x+=1;// 时间常熟
//执行n次
for (i=1;i<=n ;i++ ) {
    m +=2;//时间常数c
}
// 外层循环执行n次
for (i=1;i<=n ;i++ ) {
    // 内层循环执行n次
    for (j=1;j<=n ;j++ ) {
        k +=2;//时间常数
    }
}

总时间=$c_{0}+c_{1}n+c_{2}n^2=O(n^2)$

if-then-else条件语句：最坏的清下的运行时间为——条件判断的时间+最大值（then部分的语句运行时间或else部分的语句运行时间）。

// 条件：常数
if (length()==0) {
    return false;// then部分：常数
}
else{ //else部分：（常数+常数）*n
    for (int n=0;n<length() ;n++ ) {
        // 另一个if：常数+常数（无else部分）
        if(!list[n].equals(otherList.list[n])){
            return false;
        }
    }
}