《大資料算法》一第2章 時間亞線性算法

本節書摘來異步社群《大資料算法》一書中的第2章 ，第2.1節，王宏志　編著, 更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

顧名思義，時間亞線性算法就是計算時間是亞線性的算法。我們對某些有亞線性運作時間的算法很熟悉，例如，二分查找算法。需要預處理（Ω(n)）才能在亞線性時間運作的算法，稱為“僞亞線性算法”。在o(n)時間内運作，且不需要對輸入預處理的亞線性算法，稱為時間亞線性算法，這樣的算法不讀取全部輸入資料，而僅僅讀取其中的很小一部分。