Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
The following will be discussed in lecture Algorithm design - Chapter 5: Divide and Conquer II: Master theorem, integer multiplication, matrix multiplication, convolution and FFT. inviting you refer. | DIVIDE AND C ONQUER II master theorem integer multiplication matrix multiplication convolution and FFT Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley Copyright 2013 Kevin Wayne http www.cs.princeton.edu wayne kleinberg-tardos Last updated on Jul 20 2015 3 31 PM Sections 4.3-4.6 DIVIDE AND C ONQUER II master theorem Master method Goal. Recipe for solving common divide-and-conquer recurrences T n a T f n Vo Terms. a 1 is the number of subproblems. b 0 is the factor by which the subproblem size decreases. f n work to divide merge subproblems. Recursion tree. k logb n levels. a number of subproblems at level i. n I b size of subproblem at level i.