Độ phức tạp của thuật toán nhân ma trận

Question

Tôi đã đưa ra thuật toán này cho phép nhân ma trận. Tôi đọc ở đâu đó rằng phép nhân ma trận có độ phức tạp thời gian của o (n^2). Nhưng tôi nghĩ thuật toán này sẽ cho o (n^3). Tôi không biết cách tính thời gian phức tạp của vòng lặp lồng nhau. Vì vậy, hãy sửa tôi.

for i=1 to n 
    for j=1 to n  
    c[i][j]=0 
    for k=1 to n 
     c[i][j] = c[i][j]+a[i][k]*b[k][j] 

Answer 1

Thuật toán ngây thơ, đó là những gì bạn đã có khi bạn sửa nó như được ghi trong chú thích, là O (n^3).

Có tồn tại các thuật toán giảm bớt phần này, nhưng bạn không thể tìm thấy triển khai O (n^2). Tôi tin rằng câu hỏi về việc thực hiện hiệu quả nhất vẫn còn mở.

Xem bài viết wikipedia này trên Matrix Multiplication để biết thêm thông tin.

Answer 2

Cách tiêu chuẩn nhân một ma trận m-by-n bằng ma trận n-by-p có độ phức tạp O (mnp). Nếu tất cả những thứ đó là "n" với bạn, thì đó là O (n^3), không phải O (n^2). EDIT: nó sẽ không được O (n^2) trong trường hợp chung. Nhưng có những thuật toán nhanh hơn cho các loại ma trận cụ thể - nếu bạn biết nhiều hơn, bạn có thể làm tốt hơn.

Answer 3

Sử dụng đại số tuyến tính, tồn tại các thuật toán đạt độ phức tạp cao hơn so với O ngây thơ (n). Solvay Strassen thuật toán đạt được một độ phức tạp O (n ^2,807) bằng cách giảm số phép nhân cần thiết cho mỗi 2x2 tiểu ma trận từ ngày 8 đến 7.

Ma trận thuật toán nhân nổi tiếng nhanh nhất là Coppersmith-Winograd thuật toán với độ phức tạp O (n ^2.3737). Trừ khi ma trận là rất lớn, các thuật toán này không dẫn đến một sự khác biệt lớn trong thời gian tính toán. Trong thực tế, việc sử dụng các thuật toán song song cho phép nhân ma trận càng dễ dàng và nhanh hơn.

Answer 4

Trong phép nhân ma trận có 3 cho vòng lặp, chúng tôi đang sử dụng kể từ khi thực hiện của mỗi vòng lặp đòi hỏi thời gian phức tạp O(n). Vì vậy, đối với ba vòng, nó sẽ trở thành O(n^3)