大家想必對「串流」這個詞並不陌生：比方說「影音串流」之類的，會有影像或音訊源源不絕地輸入或輸出。在 C++ 裡面也有所謂的檔案串流，作業系統會先將開啟的檔案的開頭的一部分存入緩衝區，然後等待你的程式將它們逐一讀進去。

這種感覺很像是：有一連串的資料「路過了」你的程式，你的程式不需要、也不見得有足夠記憶體將所有「路過」的資料通通存下來。以演算法的角度而言，這幾年因應大資料而發展出的兩大類演算法：

優於線性時間演算法 sub-linear time algorithms

能否不看過所有資料就能夠找到足夠好的答案呢？近幾年有很多很多大學陸續開設了相關的課程。比方說 MIT Survey、Tel-Aviv University 、Columbia University 、U Texas。顯然對於大部分的問題而言，不看過所有輸入的資料無法精準回答正確答案（比方說找最大值等等），但是利用機率與一些對資料分佈的假設，不用看過所有輸入資料，也可以根據理論找出足夠好的答案。

串流演算法 streaming algorithms

與優於線性時間相對的，則是存不下所有輸入的少於線性空間 sub-linear space。但為什麼這系列的演算法不叫做 sub-linear space algorithms 呢？原因是，既然存不下所有的輸入，那麼一個非常合理的假設是，一個一個收到輸入之後、程式處理完就必須把它丟掉了。這樣子的計算模型我們就把它定義成串流計算模型。

什麼是 sub-linear 呢？假若輸入的資料量是 O(N)，那麼 N/log N、、log N、log log N 都是 sub-linear 啊（除以 N 以後趨近於 0）。如果硬要對串流演算法使用的空間進行嚴格定義的話，通常我們只會認可 O(polylog N) 的資料使用量、才叫做 (hard) streaming algorithms。

但是，對於由兩個參數決定的入規模：比方說一個 Graph，它有 N 個點、M 條邊（雖然 M >= N，但 M 的取值範圍可以相當廣泛，對於演算法的分析而言也常常是個重要的參數）。又或者我們考慮的輸入形式是一個 N x N 大小的矩陣，其中只有 M 個非零的數值（這樣儲存只需要 O(M) 的空間、一般來說我們也有 M >= N。）。在現實中，往往我們能夠存得下 N 筆資料、但是存不下全部長度為 M 的輸入。因此，如果一個串流演算法使用了 O(N polylog N) 的空間，那麼我們會說這個演算法是半串流演算法 (Semi-Streaming Algorithms) 的。

明天我們來看看一些經典的串流演算法吧～