与えられたコードの時間複雑さを理解する

Question

私はコード力でsimple questionをコーディングしていました。これは次のようになります。

Vasyaにはn組の靴下があります。毎日の朝、Vasyaは学校に行く前に靴下を履かなければなりません。彼が夕方に家に帰ってくると、Vasyaは使用済みの靴下を脱いで離します。毎m日（数m、2m、3m、...）のママは、Vasyaに一組の靴下を購入します。彼女は夕方に遅くなるので、Vasyaは翌日までに新しい靴下を履くことができません。 Vasyaが靴下を使い果たすまで何日連続して渡されますか？

入力

単一ラインは、2つの整数n及びm（100≤1≤N; 100≤2≤M）を含む、スペースで区切られています。

出力

印刷単一の整数 - 問題への答え。時間の複雑さがどうあるべきか

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

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

    cout << res; 
    return 0; 
} 

：

私のソリューションは、このですか？私たちがmのステップで増加しているので、O（n）は間違いありません。ログn（ベースm）ですか？しかし、元のnも時間とともに増加します！

いくつかの理由を入れてください。

Answer 1

RAM computation modelの最大の要因は、次のようになります。

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

バウンディング要因は次のようになります。

n + i < i*m解像度は私

i*m-i > n

と同じ速度でNで始まり、成長するため、

i > n/(m-1)

我々はここで整数値を扱っているので、追加のバウンドが

i >= 1

アルゴリズムは、時間の複雑さを見つけるためにO(n/m)

Answer 2

、それはとても素敵なコーディングだ... で成長するだろう、我々 1m、2m、3mのような独自の値で増分の倍数でmが追い越しているのでnの増分を無視することができるので、複数の増分を超えて追加の増分を無視することができます.... mの値をオーバーして（nのインクリメントを無視して）。 明らかにO（n/m）である。 そして、連続した日の間、女の子は靴下を使い果たしてしまいます。（m * i-res）の値を印刷することができます...