问题描述
我正在为代码部队上的简单问题进行编码.内容如下:
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 !!!
请提出一些理由.
推荐答案
RAM计算模型为:
while(res >= i*m)
{
res++;
i++;
}
边界因素将是:
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)
这篇关于了解给定代码的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!