在一個(gè)隨機(jī)數(shù)組中同時(shí)求出最大值與最小值，要求 輔助空間 O(1)【線性復(fù)雜度】,最壞情況下比較次數(shù) 3n/2, n為數(shù)組元素?cái)?shù)
| 提供一個(gè)方法：
假設(shè)待處理的數(shù)組為A[1...N]，該算法分為兩步
1.
對(duì)A中的元素做如下的比較，A[1]與A[N]，A[2]與A[N-1]，...,
A[N/2]與A[N-N/2+1](如果N為奇數(shù)，則A[N/2+1]沒(méi)有參與比較），對(duì)于每一個(gè)A[i]與A[N-i+1]，如果A[i]>A
[N-i+1]，則交換他們的值，否則，保持他們的值不變。
2. 第一步的結(jié)果是將數(shù)組A分成兩半，可以證明，最小值一定在前一半中，而最大值一定在后一半中。分別對(duì)前一半求最小值，對(duì)后一半求最大值，即得到整個(gè)數(shù)組的最大值和最小值。
對(duì)于第一步，比較次數(shù)為n/2，第二步的比較次數(shù)為n，因此整個(gè)算法的比較次數(shù)為3n/2（該算法需要嚴(yán)格的3n/2次比較，可能還存在更優(yōu)的算法，不過(guò)暫時(shí)沒(méi)想到） |
|
|