在两次比较中执行一次的循环或在一次比较中执行两次的循环中哪一个是有效的？

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)