На этом шаге мы рассмотрим особенности этого алгоритма.

Самая затратная по времени арифметическая операция в предыдущих алгоритмах - это скалярное умножение в двух начальных условиях. Оба они, подобно простой итерационной версии с тройным циклом, требуют p*q*r таких умножений. Однако небезынтересно оценить временную сложность для исходных матриц размерности n*n. В этом случае время выполнения можно определить следующей функцией:

            1,                если n ≤ 1,
    T(n) =                                            (6.6)
            8T(n/2) + 4Θ(n²), если n > 1,

поскольку методы вызывают сами себя восемь раз и должны выполнить четыре сложения матриц стоимостью порядка n². Поэтому согласно основной теореме (3.28) T(n) ∈ Θ(n^log₂8) = Θ(n³). Теперь рассмотрим алгоритм Штрассена - известный метод, который сокращает временную сложность до Θ(n^log₂7) = Θ(n^2,807...).

Метод, как и стандартный алгоритм, разбивает каждую из входных матриц на четыре блока. Таким образом, AB = C можно записать как:


   ⌈         ⌉ ⌈         ⌉     ⌈          ⌉  
    A_1,1 A_1,2    B_1,1 B_1,2        С_1,1 С_1,2
                           =                 
    A_2,1 A_2,2    B_2,1 B_2,2        С_2,1 С_2,2
   ⌊         ⌋ ⌊         ⌋     ⌊          ⌋

Цель метода - определить следующие новые матрицы, которые используют всего одну операцию умножения матриц:

    М₁ = (A_1,1 + A_2,2)(B_1,1 + B_2,2)
    М₂ = (A_2,1 + A_2,2) B_1,1
    M₃ = A_1,1 (B_1,2 - B_2,2)
    M₄ = A_2,2 (B_2,1 - B_1,1)                           (6.7)
    M₅ = (A_1,1 + A_1,2) B_2,2
    M₆ = (A_2,1 - A_1,1)(B_1,1 + B_1,2)
    M₇ = (A_1,2 - A_2,2)(B_2,1 + B_2,2).

После чего эти матрицы могут быть сгруппированы так, чтобы сформировать выходные блочные матрицы:

    C_1,1 = M₁ + M₄ - M₅ + M₇
    C_1,2 = M₃ + M₅                                  (6.8)
    C_2,1 = M₂ + M₄ 
    C_2,2 = M₁ - M₂ + M₃ + M₆.

Таким образом, в каждом рекурсивном вызове алгоритм выполняет 7 произведений и 18 сложений (или вычитаний). Поэтому оценка времени его выполнения:

            1,                 если n ≤ 1,
    T(n) =                                         (6.9)
            7T(n/2) + 18Θ(n²), если n > 1,

где T(n) = Θ(n^log₂7) = Θ(n^2,807...). Этот алгоритм для больших значений n может быть быстрее стандартного со временем выполнения Θ(n³). Однако для малых или средних матриц он может быть медленнее из-за больших постоянных множителей, имеющих значение на практике.

Наконец, теоретически входы этого алгоритма должны быть квадратными матрицами n*n, где n - степень двух. На практике эффективные реализации разбивают матрицы на множество квадратных подматриц и неоднократно применяют этот алгоритм. Более простая, но медленная альтернатива - дополнить (расширить) входные матрицы нулями до размерности 2^k*2^k.

На следующем шаге мы рассмотрим задачу укладки тримино.

Предыдущий шаг Содержание Следующий шаг