strassenversion ne demek?

Strassen Algoritması

Strassen Algoritması, matris çarpımını gerçekleştirmek için kullanılan, geleneksel yöntemlere göre daha verimli bir algoritmadır. Özellikle büyük boyutlu matrislerin çarpımında önemli performans avantajları sunar. 1969'da Volker Strassen tarafından geliştirilmiştir.

Temel Fikir:

Geleneksel matris çarpımı algoritması, iki n x n boyutundaki matrisi çarpmak için O(n³) işlem gerektirir. Strassen Algoritması ise, matris çarpımını daha küçük alt problemlere bölerek ve bu alt problemleri daha az sayıda çarpma işlemiyle birleştirerek karmaşıklığı düşürmeyi hedefler.

Algoritmanın Adımları:

Bölme: İki girdi matrisi (A ve B), her biri n/2 x n/2 boyutunda olan dört alt matrise bölünür.
Yeni Matrislerin Hesaplanması: Bu alt matrisler üzerinde 7 adet yeni matris (M1, M2, ..., M7) hesaplanır. Bu matrislerin hesaplanması, alt matrislerin toplamları ve farkları kullanılarak yapılır. En önemli nokta, bu adımda sadece 7 çarpma işleminin yapılmasıdır. Geleneksel yöntem 8 çarpma işlemi gerektirir.
Sonucun Elde Edilmesi: Sonuç matrisi (C = A x B), M1'den M7'ye kadar olan matrisler kullanılarak elde edilir. Bu adımda sadece toplama ve çıkarma işlemleri yapılır.

Karmaşıklık:

Strassen Algoritması'nın zaman karmaşıklığı O(n^log₂7)'dir. log₂7 yaklaşık olarak 2.81'e eşittir. Bu nedenle, büyük n değerleri için O(n³) karmaşıklığına sahip geleneksel matris çarpımından daha hızlıdır.

Avantajları: