對數時間計劃算法

我目前正在通過Hailperin，Kaiser和Knight的計劃書「Concrete Abstractions」。我已經編寫了如下所示的相同算法的遞歸和迭代版本。該算法用於對數量或事物進行n次操作。所以，一般來說，一起復制（操作n的東西）。例如，我可以找到3個像這樣的立方體，一起復制（* 3 3）或3個平方複製（* 2 3）。對數時間計劃算法

遞歸版本：

(define together-copies-of-linrec 
    (lambda (combine quantity thing) 
    (define together-iter 
     (lambda (combine start thing) 
     (if (= start quantity) 
      thing 
      (combine (together-iter combine (+ start 1) thing) 
        thing)))) 
     (together-iter combine 1 thing)))

迭代版本：

(define together-copies-of-linit 
    (lambda (combine quantity thing) 
    (define together-iter 
     (lambda (combine start newthing) 
     (if (= start quantity) 
      newthing 
      (together-iter combine (+ start 1) (combine newthing thing))))) 
    (together-iter combine 1 thing)))

現在，我需要寫這個算法的對數時間的版本，但我真的不知道從哪裏開始。在這種情況下，我看不出如何減少每個實例的操作使其成爲對數時間。

來源

2014-09-03 SherMM

假設combine保證是引用透明，可以通過查看整個計算作爲二進制樹寫的這個對數 - 時間版本。例如，假設呼叫(together-copies-of * 4 3)爲二進制樹（縮寫爲together-copies-oft）：

   (t * 4 3) 
        | 
       ----*----- 
      /  \ 
      /   \ 
     (t * 2 3)   (t * 2 3) 
      |     | 
     -----*-    ---*---- 
    /  \   /  \ 
(t * 1 3) (t * 1 3) (t * 1 3) (t * 1 3)

這裏的關鍵是，你不需要計算(t * 1 3)四次，你不需要計算(t * 2 3)兩次;你只需要計算一次。如果我們確保只計算每行的計算次數，那麼我們只需要每行執行O（1）次操作。由於二叉樹中的行數是元素數量的對數，這意味着我們有一個O（log n）算法的工作。

相比之下，當前的算法是這樣的：

這是什麼使你的程序（兩者）直線：其結構是一個大線，所以它一定需要線性時間。

下面的簡單程序實現了二叉樹的想法。

(define together-copies-of-log 
    (lambda (combine quantity thing) 
    (if (= quantity 1) 
     thing 
     (let ((child (together-copies-of-log combine (/ quantity 2) thing))) 
      (combine child child)))))

因爲我只是寫了快速說明概念，它有一些不足之處：

如果quantity不是2功率它失敗。
它不是尾遞歸的。

解決這些問題留給讀者練習。 :)

^{一對夫婦的澄清言論：}

^{0：爲什麼combine必須引用透明？如果不是，則將兩個調用combine更改爲一個實際上可能會改變該值，所以它不會是一個有效的轉換。}

^{1：爲什麼二元樹，而不是三元樹或任何其他樹？這是因爲combine只需要兩個參數。如果你正在爲不同的函數編寫一個版本，那麼樹會有相同的元數據。}

來源

2014-09-03 02:37:52 ikdc

對數時間計劃算法

回答

相關問題