Анализ сложности вложенных рекурсивных функций

Question

Я выписал рекурсивный алгоритм для маленькой самородной системы компьютерной алгебры, где я применяю парные сокращения к списку операндов алгебраической операции (только смежные операнды, так как алгебра некоммутативное). Я пытаюсь получить представление о сложности выполнения моего алгоритма (но, к сожалению, как физик, прошло очень много времени с тех пор, как я прошел какие-либо курсы под руководством CS, которые касались анализа сложности). Не вдаваясь в подробности конкретной проблемы, я думаю, что могу формализовать алгоритм в терминах функции f, которая является шагом «деление» и функцией g, которая объединяет результаты. Мой алгоритм будет принимать следующее формальное представление:

f(1) = 1 # recursion anchor for f 
f(n) = g(f(n/2), f(n/2)) 

g(n, 0) = n, g(0, m) = m   # recursion ... 
g(1, 0) = g(0, 1) = 1    # ... anchors for g 

     /g(g(n-1, 1), m-1) if reduction is "non-neutral" 
g(n, m) = | g(n-1, m-1)  if reduction is "neutral" 
      \ n + m    if no reduction is possible 

В этих обозначениях функции f и g получить списки в качестве аргументов и возвращает списки, с длиной входных/выходных списков будучи аргументом и правая часть вышеприведенных уравнений.

Для полной истории, фактический код, соответствующий f и g следующий:

def _match_replace_binary(cls, ops: list) -> list: 
    """Reduce list of `ops`""" 
    n = len(ops) 
    if n <= 1: 
     return ops 
    ops_left = ops[:n//2] 
    ops_right = ops[n//2:] 
    return _match_replace_binary_combine(
      cls, 
      _match_replace_binary(cls, ops_left), 
      _match_replace_binary(cls, ops_right)) 


def _match_replace_binary_combine(cls, a: list, b: list) -> list: 
    """combine two fully reduced lists a, b""" 
    if len(a) == 0 or len(b) == 0: 
     return a + b 
    if len(a) == 1 and len(b) == 1: 
     return a + b 
    r = _get_binary_replacement(a[-1], b[0], cls._binary_rules) 
    if r is None: 
     return a + b 
    if r == cls.neutral_element: 
     return _match_replace_binary_combine(cls, a[:-1], b[1:]) 
    r = [r, ] 
    return _match_replace_binary_combine(
      cls, 
      _match_replace_binary_combine(cls, a[:-1], r), 
      b[1:]) 

Я заинтересован в худшем случае число раз get_binary_replacement является называется, в зависимости от размера ops

Answer 1

Так что я думаю, что у меня есть это сейчас. Чтобы переформулировать проблему: найдите количество вызовов _get_binary_replacement при вызове _match_replace_binary с вводом размера n.

• определяет функцию g(n, m) (как в оригинальном вопросе), который отображает размер двух входов _match_replace_binary_combine до размера выходного сигнала
• определить функцию T_g(n, m), которая отображает размер двух входов _match_replace_binary_combine к общее количество вызовов g, необходимых для получения результата.Это также (в худшем случае) количество вызовов _get_binary_replacement как каждый вызов _match_replace_binary_combine вызовов _get_binary_replacement не более одного раза

Теперь мы можем рассмотреть наихудший случай и лучший случай для g:

• лучшем случае (без сокращения): g(n,m) = n + m, T_g(n, m) = 1

• худший случай (все нерусских eutral уменьшение): g(n, m) = 1, T_g(n, m) = 2*(n+m) - 1 (я определил это эмпирически)

Теперь master theorem (WP) относится:

Переход через описание на WP:

• k=1 (рекурсия анкер для размер 1)
• Мы разделили на a = 2 подзадачи размера n/2 в постоянных (d = 1) t ime
• После решения подзадач, объем работ, необходимых для объединения результатов, составляет c = T_g(n/2, n/2). Это n-1 (примерно n) в худшем случае и 1 в лучшем случае

Таким образом, следуя примеры на странице WP для основной теоремы, в худшем случае сложность n * log(n), и лучшая сложность дела n

Эмпирические испытания, похоже, подтверждают этот результат. Любые возражения против моей линии рассуждений?