时间戳

首页 > 解决方案 > 渐近分析，上限

algorithm - 渐近分析，上限

问题描述

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

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

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

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

i)n是输入的数量，对吗？还是n代表我们执行的步骤数？并f(n)表示算法？

ii）在下面的视频中，证明等式的上限2n+3可能是n^2主持人考虑c =1的，这就是为什么必须满足等式 n，>= 3而人们也可以选择c= 5 ，n=1对吗？那么，为什么在视频中的大多数情况下，演示者都在更改 的值n而不是c满足条件？有规律吗，还是随机的？我可以更改其中一个c或n(n0)满足条件吗？

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

请您帮助我理解，因为人们在不同的解释中提出了不同的想法，我想正确理解它们吗？

编辑

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

我的第一个问题是

在算法复杂性中，我们已经学会了丢弃常数并找到主导项，那么这种渐近分析是否可以证明该理论？

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

例如，这两个函数属于同一个组

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绑定在best//一个算法的情况average下worst

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

我见过这样的问题，比如找到某某算法的最坏情况时间复杂度，答案是O(n)or O(n^2)orO(log-n)等​​。

例如，如果我们考虑函数addToMySet2(n)，人们会说该函数的算法时间复杂度是O(n)，这在技术上是错误的，因为存在三个因素bound，bound type，（包括上限和严格上限）并且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 boundbest/average/worstcase

我认为我们可以考虑，当没有指出时，大 O 表示法通常描述了最坏情况时间复杂度的渐近上限。否则，也可以使用它来表示平均或最佳情况时间复杂度的渐近上限

标签： algorithmdata-structuresbig-ocomputer-sciencecomplexity-theory

解决方案

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

现在带着你的问题：

  1. 中的“较低”n是“下降”的，因为与“主导”相比，n+n^2+3当按比例放大时它可以忽略不计。n这意味着n+n^2+3和渐近地n^2表现相同。需要注意的是，即使 2 种算法具有相同的时间复杂度，但这并不意味着它们一样快。例如，一个总是比另一个快 100 倍，但具有完全相同的复杂性。

  2. (i)n可以是任何东西。它可能是输入的大小（例如，对列表进行排序的算法），但也可能是输入本身（例如，给出第 n 个素数的算法）或迭代次数等

  3. (ii) 他本可以采取任何c，他选择c=1作为他可以选择的例子c=1.618。实际上正确的表述是：

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

  1. 从n0公式是一个纯粹的数学结构。对于c>0，它是n函数f以 为界的值g。由于n可以表示任何内容（列表的大小、输入值等），因此对于n0

推荐阅读