algorithm - 使用 Little-oh(o) 和 Little Omega(ω)

Question

little-oh 和 little Omega 符号的用途/目的是什么？

尽管我完全理解符号本身及其代表的含义。我还没有看到任何一本书或算法在任何计算中使用它们，所以我不禁想知道如果不使用它们，为什么还要创建它们。

Answer 1

I can't help but wonder why were they even created if they are not used.

我认为这不正确(尽管我现在无法找到指向以下所有声明的链接)。

一方面，这些符号直接用于算法分析中出现的数学术语中。

• 例如，在 Probability and Computing: Randomized Algorithms and Probabilistic Analysis 中, 在处理 probabilistic method 的章节中，经常有关于以 1 - o(1) 概率做出某些选择的陈述(这意味着随着输入大小的增加，不选择某些东西的情况变得越来越少)。

  <

• 讨论时the sum of the harmonic series (例如，在对快速排序的分析中出现)，该术语有时以 ln(k) + α + o(1) 的形式给出。

我经常看到他们出现在讨论中:

• More exact analysis of heapsort variations有时使用像 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 而不是 Θ 的组合来表示，但这会很乏味。