我正在为 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随着时间增加!!!
请给出一些理由。
最佳答案
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)
增长
关于algorithm - 了解给定代码的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37222649/