一道C++面试题的误区
问题：寻找数组中的最小值和最大值。
一道很简单的题目，一般有下面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次取平均值）
|
|
所用时间（毫秒，GCC 4.5） |
所用时间（毫秒，VC 2010） | ||||||||
|
函数名 |
递增 |
递减 |
乱序1 |
乱序2 |
乱序3 |
递增 |
递减 |
乱序1 |
乱序2 |
访问www.zzzyk.com 试试 CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络， |
