c - 找到一个精确的函数来指示算法所采取的步数

Question

int mystery(int n) {
    int s = 0;
    int tmp = n+1;
    for (int i; i<=n; i++) {
        s = tmp + i;
        tmp = s;
    }
    return s;
}

如何确定该函数以及该函数的用途？另外，这个函数的运行时间是否可以改进？

Answer 1

上面有一些多余的代码； 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;
}