슈트라센 알고리즘: 두 판 사이의 차이

[[돈 코퍼스미스]](Don Coppersmith)와 슈무엘 위노그라드는 [[1987년]]에 또 다른 알고리즘인 '''코퍼스미스-위노그라드 알고리즘'''(Coppersmith–Winograd algorithm)을 개발했다. 이 알고리즘 역시 슈트라센 알고리즘처럼 재귀적 발상에서 나온 것으로, 시간 복잡도가 O(n^2.376)이고 2010년에 Stother가 O(n^2.3737)로 개선할 때까지 가장 빠른 알고리즘이었다. 이듬해 월리엄스가 O(n^2.3727)로 개선한 알고리즘이 현존하는 가장 빠른 알고리즘이다. [[2005년]]에는 이 알고리즘을 [[군론]]적 구성을 사용해 유도한 논문이 발표되었다.

 

* {{언어링크|en}} [http://mathworld.wolfram.com/StrassenFormulas.html MathWorld: Strassen's Formula] ([[역행렬#작은 블록으로 나눠서 계산하는 법|역행렬]] 계산에 대한 공식도 포함)

== 참고 자료 및 각주 ==