max & min
时间:2007-02-14 来源: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)
1. 总共有n个数可能为最大元,同样n个数可能为最小元
2.
1) 如果比较的2个数为新的,则可以排除2种情况。大的不可能是最小的,小的不可能是最大的
2) 如果比较的2个数为旧的,则最坏情况下只能排除一种情况。如果旧的比较的时候总是大,而新的
比旧的小,则只能排除新的不是最大的。同样如果旧的比较的时候总是小,而新的比旧的大,则只能
排除新的不是最小的。如果旧的以前是一个中间数,则一种情况也不可能排除
3) 如果比较的2个数都是旧的,最好的情况也就只能排除一种情况。
所以,要使2个new的比较最有意义,这样的机会有floor(n/2),
所以,2n - floor(n/2) = ceil(3n/2)
相关阅读 更多 +