了解给定代码的时间复杂度 [英] Understanding the time complexity of given code

问题描述

我正在为代码部队上的简单问题进行编码.内容如下:

I was coding for a simple question on codeforces. It reads like this:

Vasya有n对袜子.每天早上，Vasya在上学之前都必须穿上一双袜子.当他晚上回家时，Vasya脱下用过的袜子，将它们扔掉.妈妈每m天(每天的天数分别为m，2m，3m，...)向Vasya买一双袜子.她在傍晚这样做，所以Vasya不能在第二天之前穿上新的一双袜子.直到Vasya袜子用完了，要连续多少天?

Vasya has n pairs of socks. In the morning of each day Vasya has to put on a pair of socks before he goes to school. When he comes home in the evening, Vasya takes off the used socks and throws them away. Every m-th day (at days with numbers m, 2m, 3m, ...) mom buys a pair of socks to Vasya. She does it late in the evening, so that Vasya cannot put on a new pair of socks before the next day. How many consecutive days pass until Vasya runs out of socks?

输入

单行包含两个整数n和m(1≤n≤100； 2≤m≤100)，并用空格隔开.

The single line contains two integers n and m (1 ≤ n ≤ 100; 2 ≤ m ≤ 100), separated by a space.

输出

打印一个整数-问题的答案.

Print a single integer — the answer to the problem.

我的解决方法是:

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(以m为底)吗?但是原始的n也会随着时间而增加！！！

What should be the time complexity? Its definitely not O(n), as we are increasing in steps of m. Will it be log n (base m)? But also the original n increases with time !!!

请提出一些理由.

推荐答案

边界因素将是:

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

n + i < i*m since res starts at n and grows at the same rate as i

i*m-i > n

i > n / (m-1)

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

Since we are dealing with integer values here, an additional bound will be

i >= 1

该算法将随着O(n/m)

这篇关于了解给定代码的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！