时间戳

首页 > 解决方案 > 什么是渐近符号的松散界限？

math - 什么是渐近符号的松散界限？

问题描述

在描述松散边界时，我可以为正确的符号选择任何与渐近符号的实际值完全不接近的值吗？如果我的函数是 n^2 + n，我可以说松散的上限是 O(n^3)，我可以说松散的下限是 Ω(1)吗？这样的陈述是否有效？我什么时候知道我的松绑是否有效？

标签： mathtime-complexitycomplexity-theory

解决方案

从这里Big-O 和 Little-O Notation 之间的差异谈到 Big-O 和 little-o，可以说你的n^2+nis O(n^3)，这是一个宽松的上限。然而，大多数人会将其描述O(n^2)为更准确，并告诉您该算法实际上比O(n^3)

我认为当某些事情不完全了解时，“松散的约束”可能会出现更多。例如朴素的递归斐波那契函数：

def fibo(n):
  if n == 1 or n == 2:
    return 1
  return fibo(n-1) + fibo(n-2)

您可以说这是O(2^n)因为该函数进行了 2 次递归调用，因此它在每一步都加倍。但是，这棵“树”的一侧（如果您要扩展函数调用，它看起来有点像一棵树）将比另一侧更快地触底到基本情况，因为它是n-1vs n-2。这意味着“树”是不平衡的，因此它实际上会比O(2^n). 因此O(2^n)是一个“宽松的上限”。

寻找更紧密的界限留给读者作为练习；）

推荐阅读