一、在線算法概念

    在計(jì)算機(jī)科學(xué)中，一個(gè)在線算法是指它可以以序列化的方式一個(gè)個(gè)的處理輸入，也就是說在開始時(shí)并不需要已經(jīng)知道所有的輸入。

    相對(duì)的，對(duì)于一個(gè)離線算法，在開始時(shí)就需要知道問題的所有輸入數(shù)據(jù)，而且在解決一個(gè)問題后就要立即輸出結(jié)果。例如，選擇排序在排序前就需要知道所有待排序元素，然而插入排序就不必。

    因?yàn)樵诰€算法并不知道整個(gè)的輸入，對(duì)在線算法的研究主要集中在當(dāng)前環(huán)境下怎么做出選擇，在線算法找到的解只是局部優(yōu)異解而無法保證整體優(yōu)異。

對(duì)相同問題的在線算法和離線算法的對(duì)比分析形成了以上觀點(diǎn)。如果想從其他角度了解在線算法可以看一下 流算法（關(guān)注精確呈現(xiàn)過去的輸入所使用的內(nèi)存的量），動(dòng)態(tài)算法（關(guān)注維護(hù)一個(gè)在線輸入的結(jié)果所需要的時(shí)間復(fù)雜度）和在線機(jī)器學(xué)習(xí)。

一個(gè)很好的展示在線算法概念的例子是加拿大旅行者問題，這個(gè)問題的目標(biāo)是在一個(gè)有權(quán)圖中以最小的代價(jià)到達(dá)一個(gè)目標(biāo)節(jié)點(diǎn)，但這個(gè)有權(quán)圖中有些邊是不可靠的，可能已經(jīng)被剔除。然而一個(gè)旅行者只有到某個(gè)邊的一個(gè)端點(diǎn)時(shí)才能確定該邊是否已經(jīng)被移除了。最壞情況下，該問題會(huì)變得簡單，即所有的不確定的邊都被移除該問題將會(huì)變成通常的最短路徑問題。

二、離線算法概念

算法設(shè)計(jì)策略都是基于在執(zhí)行算法前輸入數(shù)據(jù)已知的基本假設(shè)，也就是說，算法在求解問題已具有與該問題相關(guān)的完全信息，通常將這類具有問題完全信息前提下設(shè)計(jì)出的算法成為離線算法。

在計(jì)算機(jī)科學(xué)中，在線算法是一種處理輸入數(shù)據(jù)的獨(dú)特形式，其演算過程中并不要求所有輸入數(shù)據(jù)在算法開始運(yùn)始之一刻即完備，反而可對(duì)逐步輸入的數(shù)據(jù)加以處理并在輸入完最后一項(xiàng)數(shù)據(jù)之后輸出運(yùn)算結(jié)果。與之相對(duì)的稱為離線算法，則假設(shè)輸入數(shù)據(jù)在運(yùn)算開始前已完備。舉例：選擇排序是離線算法，而插入排序則為在線算法。

注意：插入排序始終生成一個(gè)優(yōu)異的結(jié)果，也就是說一個(gè)正確排序的列表。然而對(duì)于很多問題，在線算法的性能比不上離線算法（即無法獲取優(yōu)異的結(jié)果）。如果對(duì)于同一個(gè)問題的在線算法和優(yōu)異化的離線算法的性能比率是有界的，那么這個(gè)在線算法被稱作是competitive。

并非所有在線算法都有與之對(duì)應(yīng)的離線算法。

以上就是關(guān)于在線算法和離線算法的知識(shí)希望對(duì)大家有幫助。