一道C++面试题的误区

落日映苍穹つ 2021-12-24 14:47 287阅读 0赞

**问题：寻找数组中的最小值和最大值。**

一道很简单的题目，一般有下面4种解法：

1 遍历两次，每次分别找出最小值和最大值。

2 只遍历一次，每次取出的元素先与已找到的最小值比较，再与已找到的最大值比较。

3 每次取两个元素，将较小者与已找到的最小值比较，将较大者与已找到的最大值比较。

4 分治：将数组划分成两半，分别找出两边的最小值、最大值，则最小值、最大值分别是两边最小值的较小者、两边最大值的较大者。

这4种算法，哪种效率最高，哪种最低？

后两种算法只要进行1.5\*N次比较，因而网上有不少解答都将它们列为最佳答案。但是，算法4用到了递归，而递归法函数调用的开销是很大的，这就注定了该算法的效率肯定不高。那么，**算法****3****就是最高效的吗**？还是用代码来验证吧。

后面的代码，对每种算法都实现了两个函数（假设数组长度为N）：

算法1：solve\_1a与solve\_1b，后者加入两个临时变量，编译器可以将变量储存在寄存器中，不用每次循环都要写内存。比较次数为2\*N次。

算法2：solve\_2a与solve\_2b，前者每次循环必比较2次，后者最好情况下(递减数组)只要比较1次，但最差情况下（递增数组）则要比较2次，比较次数为：N到2 \* N次。

算法3：solve\_3a与solve\_3b，前者每次循环取头尾两元素（从两头往中间取），后者取相邻两元素。比较次数为1.5 \* N次。

算法4：solve\_4a与solve\_4b，后者返回一个结构（只有两个元素），编译器优化可以通过两个寄存器返回该结构，减少写内存次数。（检查gcc产生的汇编，确认有进行该优化）。比较次数为1.5 \* N次。

下面是测试结果：（数组长度为6e7，每种测4次取平均值）

<table style="border-bottom:medium none;border-left:medium none;border-collapse:collapse;border-top:medium none;border-right:medium none;"> 
 <tbody> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:1pt solid;border-right:1pt solid;"> &nbsp;</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:1pt solid;border-right:1pt solid;" colspan="5"> 所用时间（毫秒，GCC 4.5）</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:1pt solid;border-right:1pt solid;" colspan="5"> 所用时间（毫秒，VC 2010）</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 函数名</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 递增</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 递减</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 乱序1</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 乱序2</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 乱序3</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 递增</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 递减</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 乱序1</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 乱序2</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 乱序3</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 1a 两次遍历</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 175</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 183</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 187</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 179</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 179</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 199</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 203</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 176</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 187</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 175</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 1b 两次遍历（优化）</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 175</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 179</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 171</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 171</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 172</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 183</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 234</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 175</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 187</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 172</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 2a 一次遍历</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 129</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 132</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 109</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 2b 一次遍历（优化）</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 90</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 109</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 109</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 109</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 113</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 105</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 3a 取头尾两元素</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 85</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 85</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 246</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 246</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 246</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 86</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 82</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 261</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 261</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 261</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 3b 取相邻两元素</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 93</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 101</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 238</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 242</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 238</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 93</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 101</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 258</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 257</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 253</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 4a 分治法</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 316</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 359</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 867</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 863</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 867</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 773</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 777</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 1554</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 1558</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 1558</td> 
 </tr> 
 <tr> 
 <td style="border-bottom:1pt solid;border-left:1pt solid;border-top:medium none;border-right:1pt solid;"> 4b 分治法（优化）</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 273</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 289</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 824</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 824</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 828</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 648</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 656</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 1347</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 1340</td> 
 <td style="border-bottom:1pt solid;border-left:medium none;border-top:medium none;border-right:1pt solid;"> 1339</td> 
 </tr> 
 </tbody> 
</table>

编译参数：tdm-gcc 4.5.2-dw2: g++ -O3 -s -Wextra –Wall VC 2010: cl /Ox /EHsc /nologo /W3

很明显，“**分治”法的效率远低于其它****3****种算法**。对前3种算法，将数组长度增加到1e8，并对十组随机数组进行测试，得到结果：

![image001.png][]

从上面的表和图可以看出，算法3在数组有序时，运行效率很高（但与算法2相差不大），而在乱序时，甚至比两次遍历都慢。乱序时：**算法****2****效率最高，算法1****次之，算法3****效率最低。**

算法2a和算法2b的效率差不多，有时算法2a的效率还略高。算法2a，每次循环都要比较2次，算法2b每次循环要比较1到2次，但由于前者的两次比较是无关的，后者的比较是相关的（第一次比较的结果决定是否进行第二次比较），在现代CPU“指令预测”等技术前，算法2a在某些情况下能比较算法2b更高效。

算法3的效率也不是绝对最差的，上面的随机数组是通过随机产生一些数得到，如果把它改为对数组的元素进行 “随机洗牌”，就得到下面的结果（所得的新数据与上面的数据和并，下图中第一、三列是上面的数据，第二、四列是改用“随机洗牌”后得到的新数据）：

![image003.png][]

从图可以看出，改用“随机洗牌”法得到乱序数组后，VC的结果没发生改变，GCC除了函数3a，结果也没改变，但是“3a一次取头尾两元素”却成为最高效的算法，但其效率和 “一次遍历取一个元素” 法，相差并不是太大。因而可以说，在单线程环境下，**“****一次遍历取一个元素”**这个最容易想到的方法，反而**是本题的最佳解法**。

算法上的最优，并不一定是实际上的最优，快排和堆排序就是一个典型的例子，虽然快排最坏情况下的复杂度是O(N^2)，而堆排序始终是O(N lgN)，但实际运用中，一个好的快排实现一般都比堆排序快很多。何况这4种算法的复杂度还都是O(N)。为了在最坏情况下节省0.5 \* N次比较，进行的所谓优化，得到的结果很可能与所期望的恰恰相反。

插入代码总是失败，还是给附件吧。 [找出数组的最小值和最大值 测试代码][Link 1]

转载于:https://www.cnblogs.com/flyinghearts/archive/2011/05/05/2035985.html

[image001.png]: /images/20211223/5c689a95403b43338855713fe6a6fefd.png
[image003.png]: /images/20211223/bc004728289d46cea99b13ef2b4092b3.png
[Link 1]: http://files.cnblogs.com/flyinghearts/min_max.zip