联机算法和脱机算法[Alg_001]

​

一、联机算法

1、定义

也叫在线算法，在算法执行过程中的任意时刻，只对要操作的数据进行一次扫描，扫描完成后便此后不再对已经操作过的数据进行保存和记忆。

这种算法有种特点：如果数据是储存在磁盘或者磁带上，便可以顺序地读取，无需在主存中储存数据的任何部分。

 

2、举例

在处理最大子序和的问题中，存在一种联机算法，具体实现如下（基于C）：

int MaxSubsequenceSum(const int A[ ], int N) {
    int TempSum, MaxSum;

    TempSum = MaxSum = 0;
    for (int i = 0; i < N; i++) {
        TempSum += A[i];

        if (TempSum > MaxSum) {
            MaxSum = TempSum;
        }
        else if (TempSum < 0) {
            TempSum = 0;
        }
    }

    return MaxSum;
}

 

可见，该算法的在执行过程中只对序列进行一次扫描，并且无需记忆已经操作过的数据，这就是联机算法，它对已经读入的数据，当即就可以给出最大子序和。

此外可以注意到，该算法的时间复杂度为​，空间复杂度为​，即线性时间常量空间，满足这一条件的联机算法几乎可以认为是完美的算法。

 

二、脱机算法

1、定义

也叫离线算法，在算法执行前所有的输入数据已知，换句话说，对于一个离线算法，在开始时就需要知道问题的所有输入数据，和需要进行的所有操作，而且在解决一个问题后就要立即输出结果。

 

2、举例

同样是序列最大子序和的问题，如下采用的算法便是脱机算法，具体实现（基于C）：

int MaxSubsquenceSum(const int A[], int N) {
    int TempSum, MaxSum;
    
    MaxSum = 0;
    for (int i = 0; i < N; i++) {
        TempSum = 0;
        for (int j = 0; j < N; j++) {
            TempSum = A[j];

            if (TempSum > MaxSum) {
                MaxSum = TempSum;
            }
        }
    }

    return MaxSum;
}

 

可以看出，在算法执行过程中，需要不止一次地对数据进行扫描，虽然就空间复杂度而言，依然是​，但其需要对数据进行记忆 ，需要把全部数据读入主存中。此外，算法的时间复杂度为​，相较于上文中的联机算法就稍逊一筹。

 

三、理解

由于对数据的处理方式不同，联机算法在结果的产生上便形成了较为明显的区别：

对联机算法而言，中途每一次读入数据产生的结果都是满足要求的结果，其结果的产生是基于对当前及过去的所有输入，可以理解为：“热炒热卖”、“炒多少，卖多少，炒好一盘上一盘”，相当于炒菜，这也正和“在线算法”中“在线”的意义不谋而合。

而脱机算法则是利用所有的数据参与计算，最终得到一个结果，其时间复杂度是非线性的，需要对数据多次扫描，无法像联机算法一样顺序读入并出结果，可以理解为：“菜全部做好了再开始营业”，相当于自助餐厅，Ready。

​