运行 时间计算
The Running Time Calculation
我对 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;
}
谢谢!
你是正确的,循环只 运行s N 次,但记住 i 递增并检查每个循环。因此,一旦循环 运行 N 次,它必须再检查 1 次以查看是否需要再次 运行 循环。
我对 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;
}
谢谢!
你是正确的,循环只 运行s N 次,但记住 i 递增并检查每个循环。因此,一旦循环 运行 N 次,它必须再检查 1 次以查看是否需要再次 运行 循环。