兩個不尋常循環的大O複雜性？

我有兩個單獨的代碼片段，我需要計算大O的複雜性。第一個是：兩個不尋常循環的大O複雜性？

k:=1; 
s := 4; 
while k < N do 
begin 
    k := 2 * k; 
    m:=1; 
    while m < N do 
    begin 
     for i := m to 2*m-1 do s := s + 2; 
     m := m + m; 
    end; 
end;

正確答案是N * log（N）。第二段代碼是：

m:=1; 
FOR i:=n downto 1 do 
BEGIN 
    m:=m*2; 
    y:=i MOD 2; 
    x:=m; 
    WHILE x>y DO 
    BEGIN 
    x:=x DIV 2; 
    y:=y*2 
END  
END

第二個問題的正確答案是n * n。我似乎無法讓我的數學正確。如果你可以幫助任何一個人，這將是很大的幫助。

來源

2013-02-01 Runner

讓我們來看看這第一段代碼：

k := 1; 
s := 4; 
while k < N do 
begin 
    k := 2 * k; 
    m := 1; 
    while m < N do 
    begin 
     for i := m to 2*m-1 do s := s + 2; 
     m := m + m; 
    end; 
end;

有一點要注意的是，在內環和外環是完全相互獨立的，所以我們可以分別對它們進行分析。讓我們從內部循環開始。

由於此循環運行，m的值將爲1,2,4,8,16,32等，因爲在每次迭代時m都是加倍。在循環內部，有三分之一的小循環總共運行了m次。這意味着，如果外部循環運行k次，循環的總運行時間進行由下式給出

1 + 2 + 4 + 8 + ... + 2 ^ķ

一個值得注意的是內環終止於m ≥ N。由於在迭代k上m的值是2 ^k，所以循環停止運行，只要2 ^k ≥ N。此只要k至少登錄 N.因此發生時，循環運行至多登錄 N次，所以在這裏所做的總功是

1 + 2 + 4 + 8 + ... + 2 ^LGñ = 2 ^{LG N + 1} - 1 = 2N - 1

在這裏，我使用了幾何級數，以簡化的總和的總和的公式。這意味着循環體的每次迭代都會執行Θ（N）。

現在剩下的事情是弄清楚外循環要運行多少次。請注意，與內部循環一樣，外部循環由每次迭代時加倍的變量（即，k）控制。使用類似的邏輯，我們得到這個循環將運行Θ（log N）次，因此總運行時間將是Θ（N log N）。

一些外賣：

有用提示＃1：由在大小加倍在每次迭代和停止可變當可變擊打一些限制N值將運行ö控制環路（日誌N）倍。

有用的提示＃2： 1 + 2 + 4 + ...+ 2 ^ķ = 2 ^{K + 1} - 1

現在，讓我們看一下在第二個代碼段：

m := 1; 
FOR i := n downto 1 do 
BEGIN 
    m := m * 2; 
    y := i MOD 2; 
    x := m; 
    WHILE x > y DO 
    BEGIN 
    x := x DIV 2; 
    y := y*2 
END  
END

如前，注意到變量m保持倍增每個迭代。這可能值得注意，因爲m的值將是1,2,4,8,16,32,64等。更一般地，在迭代i,m具有值2 ⁱ。

現在，讓我們看看內部循環會做多少工作。請注意，x的值從m開始，即2 ⁱ。在循環的每次迭代中，x減少兩倍。這意味着該循環的最大可能迭代次數爲log m = log 2 ⁱ = i。這當然很好，因爲它意味着內部循環總是最多運行i次！

一旦我們有了這些，確定運行時並不是很難。因爲我選自N向下計數到0，所做的總功將是至多

N +（N - 1）+（N - 2）+ ... + 2 + 1 = O（N ）

因此運行時間爲O（n 2 ）。

希望這會有所幫助！

來源

2013-10-27 00:13:46 templatetypedef

兩個不尋常循環的大O複雜性？

回答

相關問題