窮舉搜尋

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

窮舉搜尋kung4 geoi2 sau2 cam4英文brute-force search)係最原始嗰種搜尋演算法,指將手上嘅數據(事先以某啲方式排好咗)逐個逐個耖,一路耖到搵到想要嗰個為止。

基本概念[編輯]

睇埋:搜尋演算法

例如手上有一隨機次序排嘅數字,用家想要由呢個數列當中最大嗰個出嚟,用窮舉搜尋嘅話,睇嗰個人就要睇嗮個數列當中嘅每個數字,再俾出最大嗰個出嚟;呢段簡單嘅演算法用粵文寫出嚟嘅話會係[1]

  1. 如果個列入面冇數字,噉就唔會有「最大嗰個數」。
  2. 先假定個列入面第一個數字係最大嗰個。
  3. 逐個逐個噉去睇個列入面啲數字,如果撞到個數字大過而家手上嗰個「最大數字」嘅話,將新撞到呢個數字設做「最大數字」。
  4. 如果睇勻嗮個列入面啲數字嘅話,將手上嗰個「最大數字」交出嚟做答案。

上述呢個演算法用比較形式些少嘅虛擬碼寫出嚟嘅話會係噉:

// Input: A list of numbers L.
// Output: The largest number in the list L.
if L.size = 0 return null;
largest  L[0];
for each item in L, do
   if item > largest, then
      largest  item;
   return largest;

// 當中 "←" 代表指定敘述-「A ← B」即係將 A 嘅數值設做 B;
// 而 "return X" 會終止個演算法,並且將 X 嘅數值攞嚟做輸出。

廿一世紀嘅研究者一般都會嫌呢個演算法唔夠好,原因係呢個演算法喺最壞情況(worst-case)嗰陣要睇嗮成個列先至搞得掂(O(n),當中 n 係條陣列嘅長度),所以又有人諗咗第啲演算法出嚟做呢樣工作-而呢啲新演算法好多時都曉淨係睇個數字列嘅一小部份就經已搵得出想要嗰個數字。

運算概念[編輯]

睇埋:運算複雜度

睇埋[編輯]

[編輯]