数据结构（二）：算法及其描述

2018-09-06 本文已影响3人渔父歌

一、算法及其描述

1、什么是算法

数据元素之间的关系有逻辑关系和物理关系，对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。

把 具体存储结构上的操作实现方法 称为算法。

确切地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令包含一个或多个计算机操作。

一个算法具有如下特性：

有穷性：一个算法 必须总是 （对任何合法的输入值）在执行有穷步后结束，而且每一步都要在有穷的时间内完成。也就是说，一个算法对任意一组合法的输入值，在执行有穷步骤后一定能结束。
确定性：对于每种情况下算法应该执行的操作，在算法中都应该有明确的规定，使算法的执行者或阅读者能够明确其含义及如何执行。并且在任何条件下，算法只能由一条执行路径。

也就是说，对于任意一组给定的合法输入值，算法要执行的操作是确定的。
可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现。
有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入需要在算法执行中给出，而有些算法看似没有输入，实际上已经内嵌在代码中。
有输出：输出是与输入由确定关系的一组量值，是算法进行信息加工后的到的结果，这种确定关系就是算法的功能。

2、算法描述

我们有许多方法来描述一个算法，如：

设计一个算法：求解一元二次方程组
$ax^2+bx+c=0$
我们分别用文字描述和 C/C++语言来描述设计的算法：

语言描述：

计算 d = b*b - 4*a*c
如果 d > 0，则转第 5步
如果 d = 0，则转第 9步
如果 d < 0，则转第 12步
计算 x1 = (-b + sqrt(d)) / (2*a)
计算 x2 = (-b - sqrt(d)) / (2*a)
显示 x1和 x2的值
转第 13步
计算 x = (-b) / (2*a)
显示 x的值
转第 13步
显示没有实根
算法结束

C/C++语言描述

void solution(float a, float b, float c){
    float d, x1, x2, x;
    d = b*b - 4*a*c;
    if(d>0){
        x1 = (-b + sqrt(d)) / (2*a);
        x2 = (-b - sqrt(d)) / (2*a);
        printf("两个实根是：x1=%f, x2=%f\n", x1, x2);
    }
    else if(d==0){
        x = (-b) / (2*a);
        printf("一个实根是：x=%f\n", x);
    }
    else{
        printf("不存在实根\n");
    }
}

从上面的两个例子我们可以看出用 C/C++来描述的算法结构更清晰（编写的程序结构化更高，对 d的三种不同情况的处理一目了然）。

3、算法分析

在一个算法设计好后，还需要对其进行分析来确定一个算法的好坏。

算法设计的目标

正确性：要求算法能够正确地预先规定的功能和性能要求。这是最重要也是最基本的标准。
可使用性：要求算法能够方便地使用，对用户要友好。
可读性：算法应该易于人地理解。为了达到这个要求，算法的逻辑必须是清晰的、简单的，代码应该是结构化的。
健壮性：算法应该具有很好的容错性，能够对不合理的数据进行检查，不经常出现异常中断或者死机的现象。
高效率和低存储量

算法效率分析

通常由两种衡量算法效率的方法：事后统计法和事前分析估算法。

事后分析法存在以下缺点：

必须执行程序
存在其他因素掩盖算法本质

所以我们一般采用事前分析法。

一般来说，一个程序的运行速度不仅和算法有关，还和运行程序的计算机和所处计算机环境有关。所以我们需要撇开这些计算机软件、硬件有关的因素，仅考虑算法本身的效率高低。

一个算法是由控制结构（顺序、分支和循环）和原操作（固有的数据类型的操作，或者可以理解为分支和循环里要执行的操作）构成的。

为了比较同一问题的不同算法，通常从算法中选取一种对所研究的问题来说是基本运算的原操作，算法执行的时间大致为原操作的执行时间和被执行的次数的乘积。

显然，在一个算法中，执行原操作的次数越少，其运行时间也就相对地越少；执行的原操作次数越多，其运行时间也就相对地越多。

所以通常把算法中执行原操作地次数称为算法地时间复杂度，也就是说，一个算法地时间复杂度就是指其原操作在算法中反复执行的次数。

算法中基本运算次数（原操作）T(n)是问题规模 n的某个函数，记作：
$T(n)=O(f(n))$
"O"的定义为：若 f(n)是正整数 n的一个函数，则 T(n)=O(f(n))表示存在一个正整数 M，使得当 n>=n0时都满足
$|T(n)|\leq M|f(n)|$
也就是说，我们只需要求出 f(n)的最高阶，而忽略其低阶项和常系数，例如：
$O(3n^3+2n^2+n+1) \leftrightarrow O(n^3)$