方案中acc函數的時間複雜度？

-2

我一直在試圖找到一個嚴格的限制時間複雜度的這個函數就一個參數。我認爲這是O（p^2）（或者更大的θ），但我不再確定。方案中acc函數的時間複雜度？

(define (acc p n) 
    (define (iter p n result) 
    (if (< p 1) 
     result 
     (iter (/ p 2) (- n 1) (+ result n)))) 
    (iter p n 1))

來源

2012-02-13 sara hamedani

@sarahamedani，爲什麼這是O（p^2）？它看起來像O（log p）給我。運行時應該對n的值不敏感。

您正在對一系列數字進行求和，從n開始倒數。 iter將迭代的次數取決於p在不小於1的情況下可以減半多少次。換句話說，p中最左邊的'1'位的位置減1，是iter將迭代的次數。這意味着iter運行的次數與log p成正比。

來源

2012-02-13 10:58:02

只是爲了迂腐，它是在程序集O（p^2）中，純粹是從技術定義中講話。這只是它也屬於一個小得多的集合，我們試圖說服OP，O（p^2）是方式，太鬆散的上界。 – dyoo 2012-02-14 16:59:00

你可能會嘗試眼球，或更系統地去。假設我們從頭開始這樣做，我們應該嘗試從函數定義中構建一個遞歸關係。

現在我們可以假設一個非常簡單的機器模型，其中算術運算和變量查找是常量時間。

讓iter-cost是計算需要多少步驟來計算iter函數的名字，讓它成爲p功能，因爲iter的終止只取決於p。那麼你應該可以寫出iter-cost(0)的表達式。你能做到這一點爲iter-cost(1),iter-cost(2),iter-cost(3)，和iter-cost(4)？

更一般地說，如果p大於零，您能表示iter-cost(p)？它將根據常數以及對iter-cost的反覆調用。如果你可以把它表達爲一個復發，那麼你可以更好地用封閉的形式來表達它。

來源

2012-02-13 19:49:47 dyoo

方案中acc函數的時間複雜度？

回答

相關問題