在兩次比較中執行一次的循環或在一次比較中執行兩次的循環中哪一個是有效的？

Question

我想找到數組中的最小和次小數。我可以掃描兩次，或者我可以用兩次比較掃描一次。哪個有效？

Answer 1

一次掃描應該更快，因爲您可以只保留兩個分隔符變量最小和次小。您將在平均值上使用，每次迭代少於兩次比較（與使用正好2倍數量的單循環比較的2次獨立循環相比）。

在某種僞

smallest = Inf 
2ndSmallest = Inf 
for elem in array 
    if elem < smallest 
     2ndSmallest = smallest 
     smallest = elem 
    else if elem < 2ndSmallest 
     2ndSmallest = elem 
    end 
end 

凡這是假定你進入上面的，如果完全在至少兩次（你可以輕鬆地添加一個修補程序的情況下，這可能並非如此）條款。然而，討論是更喜歡的，所以我會留下寫下實際的比較實施作爲練習。

Answer 2

經驗法則：避免多次循環

拇指的第二個規則：避免過早優化（可讀性和可維護性第一）

這就是說，高效的算法

（請注意，你需要的僞代碼以處理列表大小爲空或一個的情況）：

smallest = min(list[0],list[1]) 
second_smallest = max(list[0],list[1]) 
for el in list[2:]: 
    if el < second_smallest: 
     second_smallest = max(el,smallest) 
     smallest = min(el,smallest)