Вычисление времени выполнения алгоритма разделения за 4 и подтверждением

Question

Я пишу этот код в Python:

def sub(ma):
    n = len(ma); m = len(ma[0])
    if n != m : return
    n2 = int(ceil(n/2))
    a = []; b = []; c = []; d = [] 
    for i in range(n2):
        a.append(ma[i][0:n2])
        b.append(ma[i][n2:n])
        c.append(ma[n2+i][0:n2])
        d.append(ma[n2+i][n2:n])
    return [a,b,c,d] 

def sum(ma):
        if len(ma) == 1 : return ma[0][0]
        div = sub(ma)       
        return sum(div[0])+sum(div[1])+sum(div[2])+sum(div[3]) 

Знаете ли вы, что такое, возможно, рецидивовое уравнение $ t (n) $ методом «суммы»? Я полагаю, это похоже на то, что $$ t (n) = 4t (n/2) + f (n) $$ Что это $ f (n) $? Спасибо,

Answer 1

Подпрограмма подставка Квартеры матрицы на четыре части. Это требует времени $ f (n) $, и поэтому время бега сумма (который суммирует все записи в своей входной квадратной матрице любопытным образом разделить и придерживаться) удовлетворяет повторному /2 rfloor) + 2t ( lceil n/2 rceil) + f (n) + o (1) & n> 1. end {case} $$ подпрограмма подставка довольно просто, и я уверен, что вы можете выяснить, что его время работы самостоятельно (хотя вам придется быть осторожным с семантикой списка, добавляясь в Python).