首页 > 试题广场 >

阅读以下从含有n(n=2 k )个元素的数组S中求最大元素的

[问答题]

阅读以下从含有n(n=2 k )个元素的数组S中求最大元素的算法,请问:

1)该算法采用了什么典型的算法设计策略?

2)分析算法开销,写出开销函数并求解。

Largest(n,S)
{
if n==1
   L=S[1];
else
{
   h= ën/2û;
m=n-h;
copy S[1]...S[h] to an array U;
copy S[h+1]...S[n] to an array V;
L1 = Largest(h, U);
L2 = Largest(m, V);
if (L1>L2)
L=L1;
else
    L=L2;
}
return L;
}

1)递归
2)T(2k) = 2T(2k-1) + f(2k)
                = 22T(2k-2) + 2f(2k-1) + 20f(2k)
                = ...
                = 2kT(1) + 2k-1f(2) + ... + f(2k) (设T(1) = g(n) = a,f(n) = bn)
                = a*2k + kb*2k
                = an + bnlog2n
                = O(nlog2n)
发表于 2022-03-10 22:45:18 回复(0)