关于 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正如预期的那样，在循环体内，所有语句都已标记为 。

Answer 2

这个 n 可能表示插入排序具有的外部 for 循环的时间复杂度 -> O(n^2)，而不是它的实际循环计数。