嵌套遞歸函數的複雜性分析

我已經寫出了一個小本地計算機代數系統的遞歸算法，其中我將代數運算的操作數列表中的成對還原應用於相鄰操作數列表，因爲代數是非交換）。我想了解我的算法的運行時複雜性（但不幸的是，作爲一名物理學家，自從我選修了處理複雜性分析的本科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

來源

2016-11-10 Michael Goerz

您是否嘗試應用_Master Theorem_？ https://en.m.wikipedia.org/wiki/Master-Theorem – clemens

我知道必須有一個關於此的定理！乍一看，它似乎完全適用於我的情況，我會通讀詳細信息，並瞭解我的位置 –

@macmoonshine我不認爲主定理可以直接應用。它處理'T（n）= aT（n/b）+ f（n）'類型的遞歸，但OP問題的類型爲T（n）= g（T（n/b））， T（n/c））+ f（n）'，我看不出一種簡單的方法將其減少到第一種形式......無論如何，首先要做的就是獲得'g'的複雜性，因爲它不依賴於'f'。之後，你只需用'f（n/2）'替換這個複雜性的兩個參數，然後你可以以主定理的形式結束，假設它仍然是線性的... – Bakuriu

所以我想我現在已經明白了。要重新解決問題：撥打_match_replace_binary並輸入大小爲n的輸入時，找到撥打_get_binary_replacement的電話號碼。

定義函數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（I憑經驗確定此）

現在，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

經驗性試驗似乎證實了這一結果。任何反對我的推理？

來源

2016-11-11 19:03:49

嵌套遞歸函數的複雜性分析

回答

相關問題