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 subrage 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 problems and \(n\) be the size of a subproblem.

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

a.

  1. \(T(n) = T(n / 2) + c = \Theta(\lg n)\). (master method)

  2. \(\Theta(n\lg n)\).

    \[ \begin{aligned} T(n) & = T(n / 2) + cN \\\\ & = 2cN + T(n / 4) \\\\ & = 3cN + T(n / 8) \\\\ & = \sum_{i = 0}^{\lg n - 1}(2^icN / 2^i) \\\\ & = cN\lg n \\\\ & = \Theta(n\lg n). \end{aligned} \]

  3. \(T(n) = T(n / 2) + cn = \Theta(n)\). (master method)

b.

  1. \(T(n) = 2T(n / 2) + cn = \Theta(n\lg n)\). (master method)

  2. \(\Theta(n^2)\).

    \[ \begin{aligned} T(n) & = 2T(n / 2) + cn + 2N = 4N + cn + 2c(n / 2) + 4T(n / 4) \\\\ & = 8N + 2cn + 4c(n / 4) + 8T(n / 8) \\\\ & = \sum_{i = 0}^{\lg n - 1}(cn + 2^iN) \\\\ & = \sum_{i = 0}^{\lg n - 1}cn + N\sum_{i = 0}^{\lg n - 1}2^i \\\\ & = cn\lg n + N\frac{2^{\lg n} - 1}{2 - 1} \\\\ & = cn\lg n + nN - N = \Theta(nN) \\\\ & = \Theta(n^2). \end{aligned} \]

  3. \(\Theta(n\lg n)\).

    \[ \begin{aligned} T(n) & = 2T(n / 2) + cn + 2n / 2 \\\\ & = 2T(n / 2) + (c + 1)n \\\\ & = \Theta(n\lg n). \end{aligned} \]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用