小欧(O)和小欧米茄(ω)的使用

Question

小-哦和小欧米茄符号的用途/目的是什么？

虽然我完全理解符号本身以及它们所代表的意义。我从未见过在任何计算中使用它们的一本书或算法，所以我不禁想知道，如果不使用它们，为什么还要创建它们。

Answer 1

我不禁想知道，如果它们不被使用，为什么还要创建它们呢？

我不认为这是正确的(虽然我现在无法找到与以下所有声明的链接)。

首先，这些符号直接用于分析算法时出现的数学术语。

• 例如，在概率与计算:随机算法与概率分析中，在关于概率法的章节中，经常会有一些关于使用概率1-o(1)进行某种选择的声明(这意味着随着输入大小的增加，不选择的情况变得越来越少)。
• 在讨论调和级数之和 (例如，在快速排序的分析中)时，这个术语有时被称为ln(k) +α+ o(1)。

我经常看到他们在讨论中提出：

• 堆形变化的更精确分析有时使用诸如2n log(n) (1-o (1 ))和n log(n) (1 + o(1))这样的术语(这里链接的论文没有)。
• 当对某些问题有一个实际的下限时(通过证明或由于不存在更好的解决方案)，类似于“您不能在f(n)中这样做，因为它是o( g(n) )”(等效地说，“因为g(N)是ω(f(n))")。(例如：“无法在时间n中对此进行排序，因为n log(n)是ω(N)”)。这可以通过限制或通过O而不是Θ的组合来表示，但这将是乏味的。