渐近分析，上限

Question

我对算法的渐近分析有些困惑。

我一直在努力理解这个上限情况，看过几个 youtube 视频。在其中一个中，有一个这个方程式的例子我们必须找到方程 2n+3 的上界。所以，通过观察这个，可以说它将成为 O(n).

我的第一个问题：在算法复杂性中，我们学会了舍弃常数并找到主导项，那么这个渐近分析是否可以证明该理论？还是有其他意义？否则，当它始终是等式中最大的 n 时，此分析的意义何在，例如 - 如果它是 n+n^2+3，则上限将始终是 n^2对于一些 c 和 n0.

我的第二个问题：根据规则，渐近分析中的上限公式必须满足此条件 f(n) = O(g(n)) IFF f(n) < c.g(n) 其中 n>n0,c>0, n0>=1

i) n 是输入的编号，对吧？或者 n 代表我们执行的步骤数？ f(n) 代表算法吗？

ii) 在following video中证明等式2n+3的上界可能是n^2，提出者认为c =1，这就是为什么要满足等式n 必须是 >= 3，而也可以选择 c= 5 和 n=1，对吗？那么，为什么在视频中的大多数情况下，演示者会更改 n 而不是 c 的值来满足条件？是有规律的，还是随机的？我可以更改 c 或 n(n0) 以满足条件吗？

我的第三个问题：在同一视频中，主持人提到 n0（n 不是）是步数。那是对的吗？我以为n0是图成为上界的极限（n0后，满足n所有值的条件）；因此 n0 也代表输入。

请你帮我理解一下，因为人们在不同的解释中有不同的想法，我想正确地理解他们吗？

编辑

接受的答案澄清了除第一个问题之外的所有问题。我在网上浏览了很多文章，如果其他人有同样的问题，我在这里记录我的结论。这将帮助他们。

我的第一个问题是

In algorithmic complexity, we have learned to drop the constants and find the dominant term, so is this Asymptotic Analysis to prove that theory?

不，渐近分析描述了算法的复杂性，这都是关于通过绘制数学表达式来理解或可视化一个函数或一组函数的渐近行为或尾部行为。在计算机科学中，我们用它来评估（注意：评估不是测量）算法在输入大小方面的性能。

比如这两个函数属于同一个组

mySet = set()
def addToMySet(n):
    for i in range(n):
        mySet.add(i*i)

mySet2 = set()
def addToMySet2(n):
    for i in range(n):
        for j in range(500):
            mySet2.add(i*j)

即使 addToMySet2(n) 的执行时间总是 > addToMySet(n) 的执行时间，这两个函数的尾部行为对于最大的 n，如果将它们绘制在图表中，则该图表的两个函数的趋势将是线性的，因此它们属于同一组。使用渐近分析，我们可以看到行为并将它们分组。

我错误地假设上限代表了最坏的情况。实际上，任何算法的上限都与所有最佳、平均和最坏情况相关联。所以正确的放置方式是

upper/lower bound in the best/average/worst case of an algorithm

。我们无法将算法的上限与最坏情况的时间复杂度相关联，而下限与最佳情况的复杂度相关联。但是，上限可能高于最坏情况，因为上限通常是已被证明成立的渐近公式。

我看过这样的题，比如求某某算法的最坏情况时间复杂度，答案是O(n)或O(n^2)或O(log-n)等.

例如，如果我们考虑函数 addToMySet2(n)，人们会说该函数的算法时间复杂度为 O(n)，这在技术上是错误的，因为存在三个因素 bound , bound type, (inclusive upper bound and strict upper bound) 和 case 涉及确定算法的时间复杂度。

当一个表示 O(n) 时，它是从这个渐近分析 f(n) = O(g(n)) IFF for any c>0, there is a n0>0 from which f(n) < c.g(n) (for any n>n0) 中导出的，所以我们正在考虑 upper bound 的 best/average/worst 情况。在上面的语句中缺少 case。

我认为我们可以考虑，大O符号在没有指明的情况下，一般描述的是最坏情况时间复杂度的渐近上界。否则，也可以使用它表达平均或最佳情况时间复杂度的渐近上限

Answer 1

渐近分析的重点是比较算法性能缩放。例如，如果我编写同一算法的两个版本，一个具有 O(n^2) 时间复杂度，另一个具有 O(n*log(n)) 时间复杂度，我确信 O(n*log(n)) 一个会更快n 是“大”。多大？这取决于。除非您对其进行基准测试，否则您实际上无法知道。你所知道的是，在某个时候，O(n*log(n)) 总是会更好。

现在提出您的问题：

n+n^2+3 中的“较低”n 被“丢弃”，因为当 n 与“主导”相比放大时它可以忽略不计。这意味着 n+n^2+3 和 n^2 表现相同渐近。重要的是要注意，即使 2 种算法具有相同的时间复杂度，但这并不意味着它们一样快。例如，一个可以总是比另一个快 100 倍，但具有完全相同的复杂性。
(i) n 可以是任何东西。它可能是输入的大小（例如，对列表进行排序的算法），但也可能是输入本身（例如，给出第 n 个素数的算法）或迭代次数等
(ii) 他可以选择任何 c，他选择 c=1 作为例子，因为他可以选择 c=1.618。实际上正确的表述是：

f(n) = O(g(n)) 敌我识别 for any c>0, there is a n0>0 from which f(n) < c.g(n) (for any n>n0)

公式中的n0是一个纯数学结构。对于 c>0，它是函数 f 受 g 限制的 n 值。因为 n 可以表示任何东西（列表的大小、输入值等），所以 n0

渐近分析，上限

Asymptotic analysis, Upper bound

algorithm

data-structures

big-o

computer-science

complexity-theory

编辑