运行 时间计算

Question

我对 for 循环的 运行 时间计算有疑问。

这是Java中《数据结构与算法分析》一书的“2.4.1 一个简单示例”中说明的示例。作者是马克艾伦韦斯。这是第 36 页。

书上说 "Line 2 has the hidden costs of initializing i, testing i ≤ N, and incrementing i. The total cost of all these is 1 to initialize, N+1 for all the tests, and N for all the increments, which is 2N + 2." 第 2 行是 for( int i = 1; i <= n; i++ )。我想知道为什么所有测试的代码N + 1 ≤ N。我觉得应该是N，因为测试i ≤ N需要N次。我一定是错的，但我想知道为什么。

public static int sum( int n )
{
    int partialSum;
    partialSum = 0;
    for( int i = 1; i <= n; i++ )
        partialSum += i * i * i;
    return partialSum;
}

谢谢！

Answer 1

你是正确的，循环只 运行s N 次，但记住 i 递增并检查每个循环。因此，一旦循环 运行 N 次，它必须再检查 1 次以查看是否需要再次 运行 循环。