估計

Question

我下面的在線課程中的alogrithm的運行時間增長級，我不能很好地理解如何估計這裏的算法增長的順序是一個示例

什麼順序作爲N的函數，以下代碼片段 的最壞情況下運行時間的增長情況？

Int sum = 0; 
    For (int i = 1; i <= 4*N; i = i*4) 
    for (int j = 0; j < i; j++) 
    sum++; 

任何人都可以向我解釋如何得到它

Answer 1

纔算聲明sum++;多少次被執行。

= 1 + 4 + 16 + 64 ... + 4 * N

這是一個幾何級數與4.共同因子如果術語在這一系列號爲k，然後

4^k = 4*N. 

Sum of series = (4^k - 1)(4-1) = (4*N - 1)/3. 

按照增長的順序，我們忽略了常數因素。

因此複雜度是O（N）。

Answer 2

這是相當簡單：

有外部循環的迭代log(N) + 1（對數是基4）。

讓x爲外環迭代數。內循環迭代4^x次。

因此，總的運行時間爲Sum(4^x) for x in [0..c]，其中c是log(N)這是一個geometric series，它的總和被容易地使用下式從維基計算：

Sum(4^x) for x in [1..c] = (1 - 4^c)/(1 - 4) = (4^c)/3。現在c是以4爲底的log（N），因此4^c = N。因此，總的答案是N和一些常數因子。

Answer 3

雖然搜索算法的訂單，我們找到的總步數該算法經過

這裏最裏面的循環有步驟，等於我的當前值的數量。

讓我經歷值I1，I2，I3 ......在

所以在算法的總步數是 - >> I1 + I2 + I3 + ...英寸

這裏i1，i2，i3 ... in的值分別是1,4,64 ... 4N;這是一個GP，第一項= a = 1，最後一項爲 等於4N.So該算法的複雜性是該GP中所有項的總和。

SUM = 1 + 4 + 64 + ... 4N

與n項和GP的，AR，AR^2 ... AR ^（N-1）=α（（R^N ）-1）/（r-1）= a（L * r-1）/（r-1） 其中L =最後一項;

這裏在我們的情況下，sum = 1 *（（4 * 4N）-1）/ 3 這大約是最後一項的1.33倍L SUM = 1。33 * 4N 這是N的線性階數

因此步數是N的線性函數，因此算法的複雜度爲N階;即O（n）。