瞭解給定代碼的時間複雜度

我在代碼上編碼爲simple question。它讀起來像這樣：瞭解給定代碼的時間複雜度

Vasya有n雙襪子。在每天早上，瓦西亞在上學之前必須穿上一雙襪子。當他晚上回家時，Vasya脫掉舊襪子扔掉。每一天（在數字m，2m，3m ......的日子），媽媽都會向Vasya買一雙襪子。她在晚上做得很晚，所以Vasya在第二天之前不能穿上新的襪子。在Vasya用完襪子之前，連續有多少天過去？

輸入

單一行包含兩個整數n和m（1≤N≤100; 2≤米≤100），用空格隔開。

輸出

打印一個整數 - 答案的問題。

我的解決辦法是這樣的：

int main() 
{ 
    int res,i,n,m; 
    cin >> n >> m; 

    i = 1; 
    res = n; 
    while(res >= i*m) 
    { 
     res++; 
     i++; 
    } 

    cout << res; 
    return 0; 
}

應該是什麼時間複雜度？它絕對不是O（n），因爲我們正在逐步增加m。它會記錄（基準米）？但也是原來的n隨着時間而增加！

請說明一些理由。

來源

2016-05-14 Insane Coder

可能重複[大O，你如何計算/近似它？] （http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it） –

在RAM computation model最大的因素將是：

while(res >= i*m) 
{ 
    res++; 
    i++; 
}

邊界因素將是：

n + i < i*m因爲水庫開始於n和以同樣的速度增長，我

i*m-i > n

i > n/(m-1)

由於我們在這裏處理的整數值，額外的結合將是

i >= 1

該算法將O(n/m)

來源

2016-05-14 04:57:53 bashrc

這是一個非常好的編碼... 增長找時間複雜度，我們在這裏可以忽略n的增量，因爲m正在追隨其自身值的倍數，如1m，2m，3m，所以我們可以忽略多個增量的額外增量....所以while循環將迭代到這個倍數m越過n的值（忽略n的增量）。 And comple xity顯然是O（n/m）。而對於連續的日子dat女孩將用盡襪子ü可以打印（m * i-res）的值...

來源

2016-05-14 05:32:22 RahulCoffee

我不同意「非常好的編碼」。原始問題是可以解決的，沒有循環和時間複雜度O（1）。 –

如果你有更好的方式，請發佈它。 – RahulCoffee

問題不是「如何最好地解決問題」，而是「這個算法的複雜性是什麼？」所以直接發佈將是無關緊要的。請參閱（http://codeforces.com/blog/entry/13465?locale=en）以獲得計算沒有循環的時間的公式。 –

瞭解給定代碼的時間複雜度

回答

相關問題