對求最大 最小值的算法複雜度分析與算法設計
文章目錄
-
-
- 對求最大 最小值的算法複雜度分析與算法設計
-
- 題目
- 總結
- 線性搜尋
- 略微改進
- 遞歸版本
-
- 結論
- 成對比較
-
- 結論
- 四種版本的pk
-
題目
對于一個個數為n的數組，如何讓元素的比較次數最少的同時擷取到最大最小值？要求比較次數小于 3 ∗ n 2 \frac{3*n}{2} 23∗n次？
總結
| 算法 | 平均比較次數 | 最好情況 | 最壞情況 |
|---|---|---|---|
| 線性搜尋 | 2*（n-1) | 2*（n-1) | 2*（n-1) |
| 略微改進的線性搜尋 | 2 ∗ ( n − 1 ) − ln n + 1 2*(n-1) - \ln{n} +1 2∗(n−1)−lnn+1 | n-1 | 2*(n-1) |
| 遞歸版本的歸并 | 介于 3 ∗ n 2 \frac{3*n}{2} 23∗n和 5 ∗ n 3 \frac{5*n}{3} 35∗n之間 | 3 ∗ n 2 \frac{3*n}{2} 23∗n | 5 ∗ n 3 \frac{5*n}{3} 35∗n |
| 成對比較 | 3 ∗ n 2 − 2 \frac{3*n}{2} -2 23∗n−2 | 3 ∗ n 2 − 2 \frac{3*n}{2}-2 23∗n−2 | 3 ∗ n − 3 2 \frac{3*n-3}{2} 23∗n−3 |
線性搜尋
這個顯然不是答案
public Map.Entry<Integer, Integer> lineSearch()
{
if (size == 0)
{
return null;
}
int max = ar[0];
int min = ar[0];
for (int i = 1; i < size; i++)
{
if (ar[i] > max)
{
max = ar[i];
}
if (ar[i] < min)
{
min = ar[i];
}
}
return Map.entry(max, min);
}
略微改進
改進的理由是如果ar[i] > max, 那麼就不用再進行第二次比較了。
最優的情況為遞增序列，隻需進行n-1次比較，這是其他方法都做不到的。然而這種情況的機率實在是有點小。
public Map.Entry<Integer, Integer> improvedLineSearch()
{
if (size == 0)
{
return null;
}
int max = ar[0];
int min = ar[0];
for (int i = 1; i < size; i++)
{
if (ar[i] > max)
{
max = ar[i];
}
else if (ar[i] < min)
{
min = ar[i];
}
}
return Map.entry(max, min);
}
對上述代碼平均比較次數的分析
記 C ( k ) 為前 k 次的比較次數， m a x ( k ) 為前 k 個元素中的最大值， m i n ( k ) 同理 C ( k + 1 ) = { C ( k ) + 1 , m a x ( k + 1 ) = a r [ k + 1 ] C ( k ) + 2 , e l s e 注意到 m a x ( k + 1 ) = a r [ k + 1 ] 的機率是 1 k + 1 是以平均情況下 C ( k + 1 ) = C ( k ) + 1 k + 1 + k k + 1 ∗ ( C ( k ) + 2 ) = C ( k ) + 2 − 1 k + 1 注意到 C ( 1 ) = 0 根據遞推公式解得 C ( n ) = 2 ∗ ( n − 1 ) − ∑ k = 2 n 1 k 近似等于 2 ∗ ( n − 1 ) − ln n + 1 記 C(k) 為前k次的比較次數，max(k)為前k個元素中的最大值，min(k)同理 \\ C(k + 1) = \begin{cases} C(k) + 1 , & max(k+1) = ar[k+1] \\ C(k) + 2, & else \end{cases} \\ 注意到max(k + 1) = ar[k+1] 的機率是 \frac{1}{k+1} \\ \begin{split} 是以平均情況下C(k + 1) &= \frac{C(k) + 1}{k+1} +\frac{k}{k+1}*(C(k) + 2) \\ &= C(k) + 2 - \frac{1}{k+1} \\ \end{split}\\ 注意到 C(1) =0 \\ 根據遞推公式解得 \\ C(n) = 2*(n - 1) -\sum_{k = 2}^{n}\frac{1}{k} \\ 近似等于 2*(n-1) - \ln{n} +1 記C(k)為前k次的比較次數，max(k)為前k個元素中的最大值，min(k)同理C(k+1)={C(k)+1,C(k)+2,max(k+1)=ar[k+1]else注意到max(k+1)=ar[k+1]的機率是k+11是以平均情況下C(k+1)=k+1C(k)+1+k+1k∗(C(k)+2)=C(k)+2−k+11注意到C(1)=0根據遞推公式解得C(n)=2∗(n−1)−k=2∑nk1近似等于2∗(n−1)−lnn+1
程式設計驗證
public class Test1
{
public static void main(String[] args)
{
MyArrayList ar = new MyArrayList();
Random random = new Random(new Date().getTime());
int N = 10000;
for (int i = 0; i < N; i++)
{
ar.add(random.nextInt(-10000, 10000));
}
Map.Entry map = ar.improvedLineSearch();
System.out.println("實際比較次數" + ar.sum);
System.out.println("估算比較次數" + (2*(N-1) - Math.log(N) +1));
System.out.println("the max: "+ map.getKey());
System.out.println("the min: "+ map.getValue());
}
}
結果
遞歸版本
算法思路：
通過遞歸方式，先将大數組分為左右兩半，再将左右兩部分各自分為左右兩部分，依次進行下去，
直到最後隻剩下一個元素或者隻剩下兩個元素的時候。當隻剩下一個元素的時候，最大值與最小值都
是本身，無需進行比較，比較次數為0.當隻剩下兩個元素的時候，隻需要經行一次比較，就可以求出
最大值與最小值，比較次數為1.而對于兩個最大值最小值對（總共4個元素，2個小，2個大）來說，
需要進行2次比較，才能得到最終的最大值與最小值。
private Map.Entry<Integer, Integer> getMaxAndMin(int[] ar, int lo, int hi)
{
int max, min;
if (hi == lo)
{
return Map.entry(ar[lo], ar[hi]);
}
else if (hi == lo + 1)
{
if (ar[lo] > ar[hi])
{
return Map.entry(ar[lo], ar[hi]);
} else
{
return Map.entry(ar[hi], ar[lo]);
}
}
int mid = (lo + hi)/2;
Map.Entry<Integer, Integer> leftEntry = getMaxAndMin(ar, lo, mid);
Map.Entry<Integer, Integer> rightEntry = getMaxAndMin(ar, mid+1, hi);
if (leftEntry.getKey() > rightEntry.getKey())
{
max = leftEntry.getKey();
}
else
{
max = rightEntry.getKey();
}
if (leftEntry.getValue() < rightEntry.getValue())
{
min = leftEntry.getValue();
}
else
{
min = rightEntry.getValue();
}
return Map.entry(max, min);
}
由此可以得到遞推公式
記 n 個元素的比較次數為 C ( n ) , 由歸并的遞歸有： C ( 1 ) = 0 , C ( 2 ) = 1 記n個元素的比較次數為C(n),由歸并的遞歸有：\\ C(1) = 0 \ , C(2) = 1 \\ 記n個元素的比較次數為C(n),由歸并的遞歸有：C(1)=0 ,C(2)=1
如果記n = 2 k + m 2^k+m 2k+m, 則有下面的公式
是以 C ( n ) = C ( ⌊ n / 2 ⌋ ) + C ( ⌈ n / 2 ⌉ ) + 2 = C ( n / 2 ) + C ( ( n + 1 ) / 2 ) + 2 = C ( n / 4 ) + C ( ( n + 1 ) / 4 ) + C ( ( n + 2 ) / 4 ) + C ( ( n + 3 ) / 4 ) + 6 = . . . . . . = C ( n / 2 k ) + C ( ( n + 1 ) / 2 K ) + C ( ( n + 3 ) / 2 k ) + . . . + C ( ( n + 2 k − 1 ) / 2 k ) + 2 k + 1 − 2 \begin{split} 是以 C(n) &= C(\lfloor n/2 \rfloor) + C(\lceil n/2 \rceil) + 2 \\ &= C(n/2) + C((n+1)/2) + 2 \\ &= C(n/4)+C((n+1)/4)+C((n+2)/4)+C((n+3)/4) + 6\\ &= ...... \\ &= C(n/2^{k})+C((n+1)/2^K)+C((n+3)/2^k)+...+C((n+2^k-1)/2^k) + 2^{k+1} - 2 \\ \end{split} 是以C(n)=C(⌊n/2⌋)+C(⌈n/2⌉)+2=C(n/2)+C((n+1)/2)+2=C(n/4)+C((n+1)/4)+C((n+2)/4)+C((n+3)/4)+6=......=C(n/2k)+C((n+1)/2K)+C((n+3)/2k)+...+C((n+2k−1)/2k)+2k+1−2
在随機等機率的情況下，即 m 在 ( 0 , 2 k ] 中任意取值， 則最後一個式子的自變量将有一半的值為 1 ，一半的值為 2 ， 對應的值有一半為 0 ，一半為 1 即 C ( n ) ‾ = 2 k + 1 + ( 1 / 2 ) ∗ 2 k = ( 5 / 2 ) ∗ 2 k 更具體的分析是，有 m 個元素對應的值為 1 ， 2 k − m 個元素對應的值為 0 故 C ( n ) = 2 k + 1 + m − 2 在随機等機率的情況下，即m在(0, 2^k]中任意取值，\\ 則最後一個式子的自變量将有一半的值為1， 一半的值為2，\\ 對應的值有一半為0，一半為1 \\ 即 \overline{C( n)} = 2^{k+1} + (1/2) * 2^k = (5/2)*2^k \\ 更具體的分析是，有m個元素對應的值為1， 2^k-m個元素對應的值為0 \\ 故C(n) = 2^{k+1} + m - 2 在随機等機率的情況下，即m在(0,2k]中任意取值，則最後一個式子的自變量将有一半的值為1，一半的值為2，對應的值有一半為0，一半為1即C(n)=2k+1+(1/2)∗2k=(5/2)∗2k更具體的分析是，有m個元素對應的值為1，2k−m個元素對應的值為0故C(n)=2k+1+m−2
盡管如此，上面的公式還是不精确的，因為對于遞歸樹不可能存在某個節點的兩個孩子節點的值都為1，否則這個節點值為2，早已結束遞歸了。
結論
根據進一步計算，最後的結果是
i f n = 2 k + m , 0 < m ≤ 2 k C ( n ) = { 3 ∗ 2 k − 1 − 2 + 2 m , m < 2 k − 1 2 k + 1 − 2 + m , m ≥ 2 k − 1 if \ n=2^k+m, 0<m\le{2^k} \\ C(n) = \begin{cases} 3*2^{k-1} - 2 + 2m &, m < 2^{k - 1} \\ 2^{k+1} - 2 +m & ,m\ge{2^{k-1}} \end{cases} if n=2k+m,0<m≤2kC(n)={3∗2k−1−2+2m2k+1−2+m,m<2k−1,m≥2k−1
這個公式非常完美的與結果符合
代碼驗證
public static void main(String[] args)
{
MyArrayList ar = new MyArrayList();
Random random = new Random(new Date().getTime());
int N = 10000;
for (int i = 0; i < N; i++)
{
ar.add(random.nextInt(-10000, 10000));
}
Map.Entry map = ar.getMaxAndMin();
System.out.println("實際比較次數" + ar.sum);
int k = (int) (Math.log(N-1) / Math.log(2));
int m = N - (int) Math.pow(2, k);
int y;
if (m < (int) Math.pow(2, k-1))
{
y = (int) (3*Math.pow(2, k-1))-2+2*m;
}
else
{
y = (int)(Math.pow(2, k+1)) - 2+m;
}
System.out.println("估計比較次數是" + y);
// System.out.println("估算比較次數" + (2*(N-1) - Math.log(N) +1));
System.out.println("the max: "+ map.getKey());
System.out.println("the min: "+ map.getValue());
}
結果
成對比較
遞歸雖然想法簡單，但是分析實在複雜，而且很有可能出現棧溢出的風險。嘗試使用自底向上的歸并
來求最大值與最小值。容易想到，隻需要對每兩個元素進行一次比較，就能得到它們中的最大值和最
小值，可以将第一對的最大值最小值對，依次與其他對的最大值最小值進行兩次比較，當到達數組末
尾的時候，就是最後的結果。
流程如上圖，注意虛線畫出來的是假想的最大值最小值對，實際上并不需要空間去存儲。
- 如果是奇數個元素：max和min初始化為 ar[0]
- 偶數個需要一次比較：max 為其中大的，min為小的
- 往後每兩個元素周遊，一次比較求出它們中最大的和最小的，兩次比較用來比較它們與現存的最大值最小值對，是以每兩個元素有3次比較
public Map.Entry<Integer, Integer> getMaxAndMinIter()
{
if (size == 0)
{
return null;
}
int max;
int min;
int i;
if (size % 2 == 0)
{
i = 2;
sum++;
if (ar[0] > ar[1])
{
max = ar[0];
min = ar[1];
}
else
{
max = ar[1];
min = ar[0];
}
}
else
{
i = 1;
max = min = ar[0];
}
for (; i < size - 1; i += 2)
{
sum++;
if (ar[i + 1] > ar[i])
{
sum += 2;
if (ar[i + 1] > max)
{
max = ar[i + 1];
}
if (ar[i] < min)
{
min = ar[i];
}
}
else
{
sum += 2;
if (ar[i + 1] < min)
{
min = ar[i + 1];
}
if (ar[i] > max)
{
max = ar[i];
}
}
}
return Map.entry(max, min);
}
結論
C ( n ) = { 3 ∗ n 2 − 2 , n 為偶數 3 ∗ n − 3 2 , n 為奇數 C(n) = \begin{cases} \frac{3*n}{2} - 2 &,n為偶數 \\ \frac{3*n-3}{2}&,n為奇數 \end{cases} C(n)={23∗n−223∗n−3,n為偶數,n為奇數
代碼驗證
public static void main(String[] args)
{
MyArrayList ar = new MyArrayList();
Random random = new Random(new Date().getTime());
int N = 10000;
for (int i = 0; i < N; i++)
{
ar.add(random.nextInt(-10000, 10000));
}
Map.Entry map = ar.getMaxAndMinIter();
System.out.println("實際比較次數" + ar.sum);
int y;
if (N % 2== 0)
{
y = (3*N-4)/2;
}
else
{
y = (3*N-3)/2;
}
System.out.println("估計比較次數是" + y);
System.out.println("the max: "+ map.getKey());
System.out.println("the min: "+ map.getValue());
}
四種版本的pk
上圖
代碼
from matplotlib import pyplot as plt
n = np.linspace(10, 100000, 20)
y1 = np.subtract(n, 1)*2
# y2 = (2*(N-1) - Math.log(N) +1)
y2 = 2*np.subtract(n, 1)
y2 = np.subtract(y2, np.log(n) + 1)
k = (np.log(n-1) / np.log(2))
m = n - np.power(2, k)
y3 = np.arange(n.size)
for i in range(0, n.size):
if m[i] < np.power(2, k[i] - 1):
y3[i] = 3*(2**(k[i]-1))-2+2*m[i]
else:
y3[i] = np.power(2, k[i]+1) - 2+m[i]
y4 = n*3/2 - 2;
fig = plt.figure()
axes = fig.add_axes([0.1, 0.1, 0.8, 0.8])
axes.set_xlabel("size of array")
axes.set_ylabel("times of compare")
axes.plot(n, y1, 'r')
axes.plot(n, y2, 'bo')
axes.plot(n, y3, 'y')
axes.plot(n, y4, 'go')
axes.legend(labels = ('line', 'line2', "merge", "pair"), loc = 'lower right')
fig.show()