水塘抽樣
水塘抽樣（）是一系列的隨機算法，其目的在於從包含n個項目的集合S中選取k個樣本，其中n為一很大或未知的數量，尤其適用於不能把所有n個項目都存放到内存的情況。最常見例子為在其論文中所提及的算法R。 參照Dictionary of Algorithms and Data Structures所載的O(n)算法，包含以下步驟（假設数组S以0開始標示）： 從S中抽取首k項放入「水塘」中 對於每一個S[j]項（j ≥ k）： 隨機產生一個範圍從0…
标签：#演算法
共 2 篇文章
線上演算法
在電腦科學中，線上演算法是一種處理輸入資料的獨特形式，其演算過程中並不要求所有輸入資料在演算法開始運始之一刻即完備，反而可對逐步輸入的資料加以處理並在輸入完最後一項資料之後輸出運算結果。與之相對的稱為離線演算法，則假設輸入資料在運算開始前已完備。舉例：選擇排序是離線演算法，而插入排序則為線上演算法。 注意：插入排序始终生成一个最优的结果，也就是说一个正确排序的列表。然而对于很多问题，線上演算法的性能比不上离线算法（即无法取得最优的结果）…