课后题
Problem 4.1 (Recurrence examples)
Give asymptotic upper and lower bound for T(n) in each of the following recurrences. Assume that T(n) is constant for n≤2. Make your bounds as tight as possible, and justify your answers.

T(n)=2T(n/2)+n4
T(n)=T(7n/10)+n
T(n)=16T(n/4)+n2
T(n)=7T(n/3)+n2
T(n)=7T(n/2)+n2
T(n)=2T(n/4)+n−−√
T(n)=T(n−2)+n2
主方法情况三，T(n)=Θ(n4)
主方法情况三，T(n)=Θ(n)
主方法情况二，T(n)=Θ(n2lgn)
主方法情况一，T(n)=Θ(n2)
主方法情况一，T(n)=Θ(nlg27)
主方法情况二，T(n)=Θ(n−−√lgn)
递归树法，假设n为偶数，T(n)=n2+(n−2)2+(n−4)2+⋯+T(2)=∑n2−1i=0(n−2i)2+T(2)=Θ(n3)
Problem 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:

An array is passed by pointer. Time =Θ(1)
An array is passed by copying. Time =Θ(N), where N is the size of the array.
An array is passed by copying only the subrage that might be accessed by the called procedure. Time =Θ(q−p+1) if the subarray A[p…q] is passed.
So:

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.
Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.
二分查找

a.

T(n)=T(n/2)+c=Θ(lgn)

b.

T(n)=T(n/2)+cN=2cN+T(n/4)=3cN+T(n/8)=∑lgn−1i=0(2icN/2i)=cNlgn=Θ(nlgn) c.

T(n)=T(n/2)+cn=Θ(n)
归并排序

a.

T(n)=2T(n/2)+cn=Θ(nlgn)

b.

T(n)=2T(n/2)+cn+2N=∑i=0lgn−1(cn+2iN)=∑i=0lgn−1cn+N∑i=0lgn−12i=cnlgn+N2lgn−12−1=cnlgn+nN−N=Θ(nN)=Θ(n2)

c.
T(n)=2T(n/2)+cn+2n/2=2T(n/2)+(c+1)n=Θ(nlgn)

Problem 4.3 (More recurrence examples)
Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.

T(n)=4T(n/3)+nlgn
T(n)=3T(n/3)+n/lgn
T(n)=4T(n/2)+n2n−−√
T(n)=3T(n/3−2)+n/2
T(n)=2T(n/2)+n/lgn
T(n)=T(n/2)+T(n/4)+T(n/8)+n
T(n)=T(n−1)+1/n
T(n)=T(n−1)+lgn
T(n)=T(n−2)+1/lgn
T(n)=n−−√T(n−−√)+n
主方法情况一，T(n)=Θ(nlog34)
利用积分求和的近似

T(n)=3T(n/3)+nlgn=nΘ(1)+∑i=0log3n−1nlgn−i=nΘ(1)+n∑i=1+lgn−log3nlgn1i=Θ(nlglgn)

​
主方法情况三，T(n)=Θ(n2n−−√)
n 足够大时，可以忽略-1。所以应用主方法情况二，T(n)=Θ(nlgn)
通过积分求和的近似，类似第2问

T(n)=2T(n/2)+nlgn=nΘ(1)+∑i=0lgn−1nlgn−i=nΘ(1)+n∑i=1lgn1i=Θ(nlglgn)T(n)=2T(n/2)+nlgn=nΘ(1)+∑i=0lgn−1nlgn−i=nΘ(1)+n∑i=1lgn1i=Θ(nlglgn)
类似于练习4.4-6。T(n)=Θ(n)
通过积分求和近似。

T(n)=T(n−1)+1/n=1n+1n−1+T(n−2)=∑i=0n−11n−i+Θ(1)=∑i=1n1i+Θ(1)=Θ(lgn)
递归树结构类似第7问

T(n)=lgn+T(n−1)=∑i=0n−1lg(n−i)=∑i=1nlgi+Θ(1)=Θ(lg(n!))=Θ(nlgn)
同样利用到积分求和的近似

T(n)=1lgn+1lg(n−2)+…+Θ(1)=∑i=0n/2−11lg(n−2i)=∑i=2n1lgi=∑i=1lgn1i=Θ(lglgn)
令 S(n)=T(n)n​，则 S(n)=S(n−−√)+1​。考虑 n=2m​ 的情况，有 S(2m)=S(2m/2)+1​。令 P(m)=S(2m)​，得 P(m)=P(m/2)+1​。 根据主定理情况二，P(m)=Θ(lgm)​。 则
T(n)=nS(n)=nS(2m)=nP(m)=Θ(nlgm)=Θ(nlglgn)

Problem 4.4 (Fibonacci numbers)
This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.22). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) F as

F(z)>=∑i=0∞Fizi=0+z+z2+2z3+3z4+5z5+8z6+13z7+21z8+…,>>

where Fi is the ith Fibonacci number.
Show that F(z)=z+zF(z)+z2F.
Show that

F(z)>>=z1−z−z2=z(1−ϕz)(1−ϕ^z)=15–√(11−ϕz−11−ϕ^z)>>
where

ϕ=1+5–√2=1.61803…>ϕ^=1−5–√2=−0import random

class GoodChip:
def good(self):
return True

def check(self, other):
    return other.good()

class BadChip:
def good(self):
return False

def check(self, other):
    return [True, False][random.randint(0, 1)]

def jig(a, b):
return [a.check(b), b.check(a)]

def diogenes(chips, verbose = False):
def find_single(chips):
if len(chips) <= 2:
return chips[0]
else:
halfpoint = len(chips) // 2
pairs = zip(chips[0:halfpoint], chips[halfpoint:halfpoint * 2])
kept = [a for (a, b) in pairs if jig(a, b) == [True, True]]

        if len(chips) % 2 == 1:
            kept.append(chips[-1])

        return find_single(kept)

good = find_single(chips)
return [chip for chip in chips if jig(good, chip)