对求最大 最小值的算法复杂度分析与算法设计
文章目录
-
-
- 对求最大 最小值的算法复杂度分析与算法设计
-
- 题目
- 总结
- 线性搜索
- 略微改进
- 递归版本
-
- 结论
- 成对比较
-
- 结论
- 四种版本的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()