max & min

ffjnfj

同时找到n个元素中的最大和最小元，在最坏情况下ceil(3n/2)是必须的.
1. 总共有n个数可能为最大元，同样n个数可能为最小元
2.
1) 如果比较的2个数为新的，则可以排除2种情况。大的不可能是最小的，小的不可能是最大的
2) 如果比较的2个数为旧的，则最坏情况下只能排除一种情况。如果旧的比较的时候总是大，而新的
比旧的小，则只能排除新的不是最大的。同样如果旧的比较的时候总是小，而新的比旧的大，则只能
排除新的不是最小的。如果旧的以前是一个中间数，则一种情况也不可能排除
3) 如果比较的2个数都是旧的，最好的情况也就只能排除一种情况。
所以，要使2个new的比较最有意义，这样的机会有floor(n/2),
所以，2n - floor(n/2) = ceil(3n/2)
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/24796/showart_247452.html