Временная сложность алгоритмов с рекурсией

Question

A - матрица размером n на n. Рассмотрим функцию algo (A), которая возвращает:

def algo(A):
    return algo(A[:n//2, :n//2]) + algo(A[:n//2, n//2:]) + algo(A[n//2:, :n//2]) + \
           algo(A[n//2:, n//2:]) + A.transpose() * A

Формула сложности времени имеет вид O(log(a*n) + n^b). Вопрос просит решить a и b. Я понял, что из-за умножения матриц, b = 3. Но что это? Не могли бы вы дать мне подсказку? Спасибо!

Answer 1

Сначала мы учтем, что умножение матриц занимает O (n ^ 3).

Всегда звоним algo, звоним снова с четвертью А.

    T(algo(A))
        |___________
        | | | |     |       
1.     algo(A/4)  O(n³) = 4T(algo(A/4)) + O(n^3)
2.        .
...       .
log(n).   .

В строке 1 у нас 4 вызова, в строке 2 - 16 вызовов, в строке i , у нас 4 ^ (i) вызовов.

Общее количество вызовов algo составляет C = 4 ^ 1 + ... + 4 ^ log (n), поскольку каждую строку мы умножаем вызовы предыдущей строки на 4, поэтому мы можем связать ее с:

C = 4^log(n)
C = log(x)      so 2^x = 4^log(n) = 2^(2*log(n))
C = log( 2*log(n) )

Общая сложность составляет O (Cn³), поскольку каждый вызов выполняет операцию O (n³).

Если общая сложность имеет форму O ( log (a * n) + n ^ b), то мы можем упростить:

O ( log (2 log (n)) * n³) = O ([1 + log ( log ( n))] n³) = O (n³ + log ( log (n)) n³).

Поскольку n³ находится вне функции log , мы можем заставить его войти:

O (n³ + log ( log (n)) n³) = O (n³ + log ( log (n ) * 2 ^ (n ^ 3))).

Если log ( log (n) * 2 ^ (n ^ 3)) = a * n,

a = [ log ( log (n) * 2 ^ (n ^ 3))] / n ,

b = 3 .

Answer 2

Если размер A будет N = n^2, то временная сложность algo будет T(N) = 4T(N/4) + N^1.5, если умножение выполняется в простом случае (я имею в виду, что мы можем использовать нечто более умное, например алгоритм Штрассена). ). Теперь из основной теоремы мы знали, что T(N) = \Theta(N^1.5) = \Theta(n^3).

Следовательно, a может быть любым постоянным значением.