На этой неделе я реализовал алгоритм рекурсивного умножения матриц, а также алгоритм Штрассена.
Что такое алгоритм Штрассена? Основная идея алгоритма Штрассена та же, что и идея использования метода «разделяй и властвуй». Мы хотим уменьшить временную сложность нашего кода. Наивный алгоритм представляет собой вложенный цикл for с временной сложностью Θ(n³), и, конечно же, нам нужно что-то более быстрое. Вот почему мы используем парадигму «разделяй и властвуй». Тем не менее, наш рекурсивный алгоритм будет не лучше, чем нерекурсивный алгоритм, и это потому, что у нас есть T(n) = 8T(n/2) + Θ(n²), временная сложность будет Θ(n³) мастером. случай теоремы 3.
Здесь в дело вступает алгоритм Штрассена и говорит: ХАААААААААААААААААААААААААААААААААААААААААААУ У меня есть идея получше, мы можем уменьшить наши умножения с восьми до семи, конечно, у нас будет еще несколько сложений, но это сделает наше дерево чуть менее густым. Это уменьшит нашу временную сложность до Θ(n^(2.8)).
Идея, стоящая за ними обоими, в чем-то одинакова. Мы делим каждую матрицу на четыре подматрицы, а затем делаем то же самое для всех из них, пока наша подматрица не будет иметь только одно значение, затем мы возвращаем произведение двух последних матриц.
Пока что я написал оба этих алгоритма на Golang, и вы можете взглянуть на них здесь. Но, к сожалению, все мои усилия были бесполезны, и вы можете спросить, почему? Поскольку он намного длиннее, чем нерекурсивные и наивные алгоритмы, я много часов пытался оптимизировать его, но моих знаний было недостаточно, и в итоге я ничего не добился.
У меня есть свои догадки, и одна из них — это само создание моих матриц. Из-за рекурсивной процедуры я не мог использовать массивы в Golang, и я знал только один способ сделать 2D-срезы в Go, и это было использование метода make, а затем диапазона for. Это довольно хлопотно и делало мой код слишком медленным (наивный алгоритм вычислял ответ за 10 секунд, рекурсивный алгоритм — около 4 минут, а алгоритм Штрассена — около 2 минут).
Итак, наконец, мне не удалось достичь своей цели, и я буду искренне благодарен, если кто-нибудь поможет мне решить эту проблему.
