algorithm - 了解给定代码的时间复杂度

Question

我正在为 simple question 编码在 codeforces 上。它是这样写的:

Vasya 有 n 双 socks 。每天早上，瓦夏在上学前都要穿上一双 socks 。当他晚上回到家时，Vasya 将用过的 socks 脱下并扔掉。每第 m 天(在编号为 m,⟩2m,⟩3m,⟩... 的日子)妈妈给 Vasya 买一双 socks 。她在晚上洗得很晚，这样 Vasya 才能在第二天之前穿上一双新 socks 。连续多少天 Vasya 的 socks 用完了？

输入

单行包含两个整数n和m(1 ≤ n ≤ 100；2 ≤ m ≤ 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 为步长增加的。会是log n (base m)吗？而且原来的n随着时间增加!!!

请给出一些理由。

Answer 1

RAM computation model 的最大因素会是:

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

边界因子将是:

n + i < i*m因为 res 从 n 开始并且以与 i 相同的速率增长

i*m-i > n

i > n / (m-1)

由于我们在这里处理整数值，因此将有一个额外的界限

i >= 1

算法将随着 O(n/m) 增长