int mystery(int n) {
int s = 0;
int tmp = n+1;
for (int i; i<=n; i++) {
s = tmp + i;
tmp = s;
}
return s;
}
如何确定该函数以及该函数的用途?另外,这个函数的运行时间是否可以改进?
最佳答案
上面有一些多余的代码; s
是完全没有必要的。重写它而不使用它会使它更清晰。
int mystery(int n) {
int tmp = n + 1;
for (int i = 1; i<=n; i++) {
tmp += i;
}
return tmp;
}
它的作用是
- 将
tmp
设置为 n + 1 - 添加 1,然后添加 2,然后添加 3,然后添加 4,依此类推
当前的运行时间为O(n)
。然而事实证明,有一个constant time formula对于 1 + 2 + 3 + ... + N
。我们可以用它来创建以下内容,即恒定时间。
int mystery(int n) {
int triangleNumber = (n * (n + 1)) / 2;
return triangleNumber + n + 1;
}
关于c - 找到一个精确的函数来指示算法所采取的步数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39823125/