最大-最小问题

问题：分析算法以从数组中找到最大和最小元素。

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）时, 递归将停止

将等式4放入等式3。

比较次数需要对n个元素/项目应用除法和征服算法=

比较次数需要对n个元素应用一般方法=（n-1）+（n-1）= 2n-2

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

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

方法1：要求（2n-2）, （2×8）-2 = 14比较方法2：要求

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