计算上限算法的步骤
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 constantc
such thatf(n)
is always≤ c · g(n)
, for sufficiently largen
(i.e. ,n ≥ n0
for 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绑定,不一定是紧的)。