计算上限算法的步骤
Counting the steps of an algorithm for an upper bound
我知道如果我有一个 for 循环和一个嵌套的 for 循环，它们都迭代 1 to n 次，我可以将两个循环的 运行 次相乘得到 O(n^2).这是一个干净简单的计算。但是，如果您有这样的迭代，
n = 2, k = 5
n = 3, k = 9
n = 4, k = 14
其中 k 是内部 for 循环迭代的次数。在某一时刻，它大于 n^2，然后恰好是 n^2，然后变得小于 n^2。假设你无法根据 n 确定 k，甚至 n 的这些点相距很远，你如何计算 Big-O？
我尝试绘制点。在某一时刻，我可以说它是 O(n^3)，因为有些点超过了 n^2，再往下，就是 O(n^2)。我应该选择哪一个？
您在问题中声明 k 是：
"... At one point, it is larger than n^2"
这是您问题中的不确定性（或 non-specificity），因此很难严格回答。无论如何，对于这个答案的其余部分，我们将假设您上面引述的意思是：
For all values of n, the value of k(n) is bounded from above by
C·n^2, for some constant C>0.
从这里开始，我们将此声明称为(+)。
现在，既然你提到了 Big-O 符号，我们将继续稍微宽松地定义这实际上意味着什么：
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus
there exists some constant c such that f(n) is always ≤ c · g(n),
for sufficiently large n (i.e. , n ≥ n0 for some constant n0).
即，Big-O 符号是一种在这里描述我们算法的 渐近 （限制）行为上限的方法。但是，您在问题中写道：
"And at one point, I could say it was O(n^3) since some points exceed n^2, and further down, it would be O(n^2)"
现在这是对算法的内部循环如何针对 n 的特定值进行行为的非常具体的分析，实际上与渐近分析（或 Big-O 表示法）无关.我们对算法如何针对 n 的特定值表现的细节不感兴趣，但我们是否可以找到给定 n 的算法的一些通用上限是 "sufficiently large"（n ≥ n0对于某个常数 n0).
现在，有了上面的这些评论，我们可以继续分析您的算法的渐近行为。
我们可以使用 Sigma 符号来解决这个问题，利用上面的语句 (+)，k(n) < C·n:
最后一步 (++) 遵循 Big-O 符号的定义，我们在上面粗略地陈述过。
因此，鉴于我们将您关于 k 的信息解释为 (+)，您的算法在 O(n^3) 中运行（这是 upper绑定，不一定是紧的）。
我知道如果我有一个 for 循环和一个嵌套的 for 循环，它们都迭代 1 to n 次，我可以将两个循环的 运行 次相乘得到 O(n^2).这是一个干净简单的计算。但是，如果您有这样的迭代，
n = 2, k = 5
n = 3, k = 9
n = 4, k = 14
其中 k 是内部 for 循环迭代的次数。在某一时刻，它大于 n^2，然后恰好是 n^2，然后变得小于 n^2。假设你无法根据 n 确定 k，甚至 n 的这些点相距很远，你如何计算 Big-O？
我尝试绘制点。在某一时刻，我可以说它是 O(n^3)，因为有些点超过了 n^2，再往下，就是 O(n^2)。我应该选择哪一个？
您在问题中声明 k 是：
"... At one point, it is larger than
n^2"
这是您问题中的不确定性（或 non-specificity），因此很难严格回答。无论如何，对于这个答案的其余部分，我们将假设您上面引述的意思是：
For all values of
n, the value ofk(n)is bounded from above byC·n^2, for some constantC>0.
从这里开始，我们将此声明称为(+)。
现在，既然你提到了 Big-O 符号，我们将继续稍微宽松地定义这实际上意味着什么：
f(n) = O(g(n))meansc · g(n)is an upper bound onf(n). Thus there exists some constantcsuch thatf(n)is always≤ c · g(n), for sufficiently largen(i.e. ,n ≥ n0for some constantn0).
即，Big-O 符号是一种在这里描述我们算法的 渐近 （限制）行为上限的方法。但是，您在问题中写道：
"And at one point, I could say it was
O(n^3)since some points exceedn^2, and further down, it would beO(n^2)"
现在这是对算法的内部循环如何针对 n 的特定值进行行为的非常具体的分析，实际上与渐近分析（或 Big-O 表示法）无关.我们对算法如何针对 n 的特定值表现的细节不感兴趣，但我们是否可以找到给定 n 的算法的一些通用上限是 "sufficiently large"（n ≥ n0对于某个常数 n0).
现在，有了上面的这些评论，我们可以继续分析您的算法的渐近行为。
我们可以使用 Sigma 符号来解决这个问题，利用上面的语句 (+)，k(n) < C·n:
最后一步 (++) 遵循 Big-O 符号的定义，我们在上面粗略地陈述过。
因此，鉴于我们将您关于 k 的信息解释为 (+)，您的算法在 O(n^3) 中运行（这是 upper绑定，不一定是紧的）。