最大 - 最小值问题

问题： 分析从数组中查找最大值和最小值的算法。

Algorithm: Max ?Min Element (a [])
Max:  a [i]
Min:   a [i]
For i= 2 to n do
If a[i]> max then
max = a[i]
if a[i] < min then
min: a[i]
return (max, min)

分析

方法 1： 如果我们对大小为 n 的数组应用通用方法，则所需的比较次数为 2n-2。

方法 2： 在另一种方法中，我们将问题划分为子问题，并找到每个组的最大值和最小值，现在每个组的最大值将仅与另一组的最大值进行比较，最小值与最小值进行比较。

设 n = 数组中项目的大小

设 T (n) = 在大小为 n 的数组上应用算法所需的时间。这里我们将项除以 T(n/2)。

2 这里倾向于最小与最小、最大与最大的比较，如上例所示。

T (n) = 2 T → 方程 (i)

T (2) = 1，比较两个元素/项目所需的时间。（时间以比较次数为单位衡量）

→ 方程 (ii)

将方程 (ii) 放入方程 (i)

类似地，对每个子问题或解剖结构递归地应用相同的过程

{使用递归意味着，我们将使用一些停止条件来停止算法}

当 → (方程 4) 时，递归将停止

将 equ.4 放入 equation3。

在 n 个元素/项目上应用分而治之算法所需的比较次数 =

在 n 个元素上应用通用方法所需的比较次数 = (n-1) + (n-1) = 2n-2

从这个例子中，我们可以分析，如何通过使用这种技术来减少比较次数。

分析： 假设我们有一个大小为 8 个元素的数组。

方法 1： 需要 (2n-2)，(2x8)-2=14 次比较
方法 2： 需要

很明显； 我们可以通过使用适当的技术来减少比较次数（复杂度）。