TAILIEUCHUNG - Thuật toán Algorithms (Phần 7)

Tham khảo tài liệu 'thuật toán algorithms (phần 7)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | POLYNOMIALS 53 such relationships can be challenging to solve precisely they are often easy to solve for some particular values of N to get solutions which give reasonable estimates for all values of N. Our purpose in this discussion is to gain some intuitive feeling for how divide-and-conquer algorithms achieve efficiency not to do detailed analysis of the algorithms. Indeed the particular recurrences that we ve just solved are sufficient to describe the performance of most of the algorithms that we ll be studying and we ll simply be referring back to them. Matrix Multiplication The most famous application of the divide-and-conquer technique to an arithmetic problem is Strassen s method for matrix multiplication. We won t go into the details here but we can sketch the method since it is very similar to the polynomial multiplication method that we have just studied. The straightforward method for multiplying two N-by-N matrices requires scalar multiplications since each of the elements in the product matrix is obtained by N multiplications. Strassen s method is to divide the size of the problem in half this corresponds to dividing each of the matrices into quarters each N 2 by N 2. The remaining problem is equivalent to multiplying 2-by-2 matrices. Just as we were able to reduce the number of multiplications required from four to three by combining terms in the polynomial multiplication problem Strassen was able to find a way to combine terms to reduce the number of multiplications required for the 2-by-2 matrix multiplication problem from 8 to 7. The rearrangement and the terms required are quite complicated. The number of multiplications required for matrix multiplication using Strassen s method is therefore defined by the divide-and-conquer recurrence M N 1M N 2 which has the solution M N Nlg7 N2 81. This result was quite surprising when it first appeared since it had previously been thought that multiplications were absolutely necessary for matrix .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.