دنبال روشی بهتر از استراسن که پیچیدگی زمانی اش کمتر از n به توان 3 باشد

[valentine093]

با سلام .من دنبال روشی بهتر از استراسن که پیچیدگی زمانی اش کمتر از n به توان 3 باشد میگردم و خیلی فوری میخواستم.کمکی کنین ممنون میشم

 

[solmaz24]

سلام ببخشید میشه ضرب استراسن رو با برنامه ی مطلب بنویسید؟ برای من هم خیلی فوریه

 

[soroush.]

با سلام .من دنبال روشی بهتر از استراسن که پیچیدگی زمانی اش کمتر از n به توان 3 باشد میگردم و خیلی فوری میخواستم.کمکی کنین ممنون میشم

دوست عزیز ضرب ماتریس ها در حالت معمول n^3 هست اما ما تو الگوریتم استراسن n^2.81 داریم که کمتر از n^2 است
من منظور شما رو نمی فهمم؟ می خوای الگوریتم جدید ارائه بدی یا چه؟؟؟

 

[seyed_hosein]

سلام !
این برنامه ضرب استراسن است که از روش تقسیم و غلبه استفاده می کند و دارای پیچیدگی زمانی n^2.81 است
.
امیدوارم مفید باشد.

//////////////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace Strassen
{
public partial class frm_StrassenMultiplication : Form
{
#region "global arrays"
int[,] result;
int[,] arr1, arr2;
#endregion
//defualt function for initialize components in form
public frm_StrassenMultiplication()
{
InitializeComponent();
}
//divisio of matrix until matrix with two rows and two cols for calculte result
private void mul_matrix(int x1, int y1, int x2, int y2, int x3, int y3, int n)//, int col)
{
if (n == 2)
add_matrix(x1, y1, x2, y2, x3, y3);
else
{
mul_matrix(x1, y1, x2, y2, x3, y3, n / 2);
mul_matrix(x1, y1 + n / 2, x2 + n / 2, y2, x3, y3, n / 2);
mul_matrix(x1, y1, x2, y2 + n / 2, x3, y3 + n / 2, n / 2);
mul_matrix(x1, y1 + n / 2, x2 + n / 2, y2 + n / 2, x3, y3 + n / 2, n / 2);
mul_matrix(x1 + n / 2, y1, x2, y2, x3 + n / 2, y3, n / 2);
mul_matrix(x1 + n / 2, y1 + n / 2, x2 + n / 2, y2, x3 + n / 2, y3, n / 2);
mul_matrix(x1 + n / 2, y1, x2, y2 + n / 2, x3 + n / 2, y3 + n / 2, n / 2);
mul_matrix(x1 + n / 2, y1 + n / 2, x2 + n / 2, y2 + n / 2, x3 + n / 2, y3 + n / 2, n / 2);
}
}
//calculate with strassen algorithm
private void add_matrix(int x1, int y1, int x2, int y2, int x3, int y3)
{
int p1 = arr1[x1, y1] * (arr2[x2, y2 + 1] - arr2[x2 + 1, y2 + 1]);
int p2 = (arr1[x1, y1] + arr1[x1, y1 + 1]) * arr2[x2 + 1, y2 + 1];
int p3 = (arr1[x1 + 1, y1] + arr1[x1 + 1, y1 + 1]) * arr2[x2, y2];
int p4 = arr1[x1 + 1, y1 + 1] * (arr2[x2 + 1, y2] - arr2[x2, y2]);
int p5 = (arr1[x1, y1] + arr1[x1 + 1, y1 + 1]) * (arr2[x2, y2] + arr2[x2 + 1, y2 + 1]);
int p6 = (arr1[x1, y1 + 1] - arr1[x1 + 1, y1 + 1]) * (arr2[x2+1, y2] + arr2[x2 + 1, y2 + 1]);
int p7 = (arr1[x1, y1] - arr1[x1 + 1, y1]) * (arr2[x2, y2] + arr2[x2, y2 + 1]);

result[x3, y3] += p5 + p4 - p2 + p6;
result[x3, y3 + 1] += p1 + p2;
result[x3 + 1, y3] += p3 + p4;
result[x3 + 1, y3 + 1] += p5 + p1 - p3 - p7;
}
//initialize arrays and set defualt values for it.
private void btn_Calc_Click(object sender, EventArgs e)
{
int row = Convert.ToInt16(txt_Number.Text);
//preparing lists for new values
lst_FirstArray.Items.Clear();
lst_FirstArray.Columns.Clear();
lst_SecondArray.Items.Clear();
lst_SecondArray.Columns.Clear();
lst_Result.Items.Clear();
lst_Result.Columns.Clear();
//-----------------------------------------------------
result = new int[row, row];
arr1 = new int[row, row];
arr2 = new int[row, row];
Random rnd = new Random();
for (int i = 0; i < row; i++)
{
lst_FirstArray.Columns.Add("COL" + (i + 1).ToString());
lst_SecondArray.Columns.Add("COL" + (i + 1).ToString());
lst_Result.Columns.Add("COL" + (i + 1).ToString());
lst_FirstArray.Columns.Width = 45;
lst_SecondArray.Columns.Width = 45;
lst_Result.Columns.Width = 45;
}

for (int i = 0; i < row; i++)
{
string[] str_array1 = new string[row];
string[] str_array2 = new string[row];
for (int j = 0; j < row; j++)
{
//make random numbers between -10 and 10
arr1[i, j] = rnd.Next(-2, 2);
arr2[i, j] = rnd.Next(-2, 2);
str_array1[j] += arr1[i, j].ToString();
str_array2[j] += arr2[i, j].ToString();
}
ListViewItem lst1 = new ListViewItem(str_array1);
lst_FirstArray.Items.Add(lst1);
ListViewItem lst2 = new ListViewItem(str_array2);
lst_SecondArray.Items.Add(lst2);
}
mul_matrix(0, 0, 0, 0, 0, 0, row);
for (int i = 0; i < row; i++)
{
string[] str_result = new string[row];
for (int j = 0; j < row; j++)
str_result[j] += result[i, j].ToString();

ListViewItem lst_result = new ListViewItem(str_result);
lst_Result.Items.Add(lst_result);
}
}
}
}

////////////////////////////////////////////////////////