arrays - 看不懂CLRS问题4-2案例2

Question

问题:

4-2 Parameter-passing costs

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameter-passing strategies:

1. An array is passed by pointer. Time Theta(1)

2. An array is passed by copying. Time Theta(N), where N is the size of the array.

3. An array is passed by copying only the subrange that might be accessed by the called procedure. Time Theta(q-p+1) if the subarray A[p..q] is passed.

a. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5 ). Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let N be the size of the original problem and n be the size of a subproblem.

b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.

我无法理解如何解决通过复制两种算法传递数组的情况 2 的重复出现。

以案例2的二分查找算法为例，大多数答案给出的递归是T(n)=T(n/2)+Theta(N)。我对此没有问题。

这是我在网上找到的一个看起来正确的答案:

T(n)

= T(n/2) + cN

= 2cN + T(n/4)

= 3cN + T(n/8)

= Sigma(i = 0 to lgn - 1) (2^i cN / (2^i))

= cNlgn

= Theta(nlgn)

我无法理解倒数第二行如何导致最后一行的答案。为什么不用 Theta(Nlgn) 表示呢？以及 N 如何变成 Theta 符号中的 n？

N和n感觉有些联系。我无法理解它们之间的联系以及如何将其应用到解决方案中。

Answer 1

似乎 N 代表完整的数组长度，n 是当前 block 大小。

但是当您从全长 n=N 开始时，公式实际上只利用初始值 - 例如，查看 T(n/4) 的 T(N/4)，所以 n===N 无处不在。

在这种情况下，您可以将 n 替换为 N。