上浒充通大学 Divide-and-Conquer SHANGHAI JIAO TONG UNIVERSITY Divide-and-conquer. Break up problem into several parts. e Solve each part recursively. Combine solutions to sub-problems into overall solution. Most common usage. Break up problem of size n into two equal parts of size vn. Solve two parts recursively. Combine two solutions into overall solution in linear time. ©Consequence. ·Brute force:n2. Divide et impera. Veni,vidi,vici. Divide-and-conquer:n log n. Julius Caesar3 Divide-and-Conquer Divide-and-conquer. • Break up problem into several parts. • Solve each part recursively. • Combine solutions to sub-problems into overall solution. Most common usage. • Break up problem of size n into two equal parts of size ½n. • Solve two parts recursively. • Combine two solutions into overall solution in linear time. Consequence. • Brute force: n2. • Divide-and-conquer: n log n. Divide et impera. Veni, vidi, vici. - Julius Caesar