第一次习题课.ppt

4.2-2利用递归树来证明递归式T(n)=T(n/3)+T(2n/3)+cn的解是Ω(nlgn)。其中c是一个常数。 解：该递归树不是完全二叉树，叶子节点有深有浅，最浅的叶子节点是从根结点沿着路径n→(1/3)n→(1/3)2n→...→ 1/3)kn =1,所以(1/3)kn=1,k=log3n。从该最浅的层数向上，每一层的代价都是cn，因此T(n) ≥k*cn=cn *log3n= Ω(nlgn). ? 4.3-1用主方法来给出下列递归式紧确的渐近界。 a)T(n)=4T(n/2)+n b)T(n)=4T(n/2)+n2 c)T(n)=4T(n/2)+n3 解：a=4,b=2,nlogba=n2 a) f(n)=n=O(n2-ε),所以T(n)=Θ(n2) b) f(n)=n2=Θ(n2),T(n)=Θ(n2lgn) c) f(n)=n3=Ω(n2+ε),T(n)=Θ(n3) 4.3-3用主方法证明二分查找递归T(n)=T(n/2)+Θ(1)的解是T(n)=Θ(lgn)。 解：a=1,b=2,f(n)=Θ(1)=Θ(nlogba)=Θ(1), T(n)=Θ(nlogbalgn)=Θ(lgn)。 ? 6.1-1在高度为h的堆中，最多和最少的元素个数是多少个？ 解：最多即完全二叉树，有2h+1-1个元素，最少即最低级不满可能只有2h个元素。 6.1-4在一个最大堆中，假设其所有元素都不相同，那么其最小元素可能存在于堆的哪些地方？ 解：存在于叶节点。 6.1-6序列23,17,14,6,13,10,1,5,7,12是一个最大堆吗？ 解：不是。{5,6,7}这个子树不满足最大堆定义。 6.2-2由过程MAX-HEAPIFY开始，写出进行对应的最小堆操作的MIN-HEAPIFY(A,i)过程的伪代码，并比较MIN-HEAPIFY与MAX-HEAPIFY的运行时间。 MIN-HEAPIFY(A,i) l←LEFT(i) r←RIGHT(i) if l≤heap-size[A] and A[l]A[i] then smallest←l else smallest←i if r≤heap-size[A] and A[r]A[smallest] then smallest←r if smallest≠i then exchange A[i]?A[smallest] MIN-HEAPIFY(A,smallest) 运行时间为O(lgn)。 6.2-4 对iheap-size[A]/2，调用MAX-HEAPIFY(A,i)的结果怎样？ 堆中的元素不需要调整。 6.2-5 MAX-HEAPIFY的代码效率较高，但第10行中的递归调用可能例外，它可能使某些编译程序产生低效的代码。请用迭代的控制结构(循环)取代递归结构，从而写一个更为高效的MAX-HEAPIFY。 6.4-1模仿图6-4说明HEAPSORT在数组A=5,13,2,25,7,17,20,8,4 上的操作过程。 略。 6.4-3对一个其所有n个元素已按递增排列的数组A，堆排序的运行时间是多少？若A的元素呈降序排列呢？ 对排序中，不管是元素是增序还是降序，建堆的时间为O(n),n-1调用MAX-HEAPIFY，需要时间O(nlgn)。 6.4-5证明：在所有元素都不相同时，堆排序算法的最佳运行时间是Ω(nlgn)。 堆排序算法在最坏情况下是O(nlgn)，那么在最佳情况下就是Ω(nlgn)。 因为堆排序是基于比较的排序，基于比较的排序算法最坏情况下界为Ω(nlgn)。 6.5-3 使用最小堆实现最小优先级队列，用伪代码写出HEAP-MINIMUM，HEAP-EXTRACT-MIN、HEAP-DECREASE-KEY和MIN-HEAP-INSERT过程。 HEAP_DECREASE-KEY(A,i,key) If keyA[i] then error new key is larger than current key A[i]←key while i1 and A[parent(i)]A[i] do exchange A[i]?A[parent(i)] i←parent(i) MAX-HEAP-INSERT(A,key) heap-size[A]←heap-size[A]+1 A[heap-size[A]]←+∞ HEAP-DECREASE-KEY(A,heap-size[A],key) 6.5-7 HEAP-DELETE(A,i)操作将结点i中的项从堆A中删去，对含n个元素的最大堆，请给出时间为O(nlgk)的HEAP-DELETE的实现。 7.2-2当数组A的所有元素都具有相同值时