关于 for 循环的“运行时间”的问题

Question

我开始阅读“算法导论，第三版”一书，但遇到了一些对我来说不够清楚的关于“插入排序”算法的内容。

请先看一下图片：

首先，作者定义了 n = A.length。 A.length是数组 A 的长度。

因此，假设数组“A”的长度为 5。如果我从 j = 2（如图所示）到 A.Length = 5运行for循环，我会说第一行将运行 4 次，这意味着对于任何 n，它将运行 n - 1 次。另一方面，作者写道，第一行将运行 n 次。

我错过了什么？

Answer 1

第一行可能是指检查条件的次数。如果您的循环运行n-1次数，迭代器上的条件被检查n次数（包括在最后，当它变为假时）。在循环体内，所有语句都n-1按预期标有。