algorithm - 算法的增长函数？

Question

好吧，我在这里有两个问题：-

1. 如果 f(n) 是要找到其增长率的函数，那么对于所有三个符号来说，g(n) 将是相同的，例如 f(n)=O(g(n)) 和类似的 omega 和 theta ?

2. Theta 符号是“omega 和 Oh”，如果在某些情况下 oh 和 omega 函数不同，那么我们将如何在那里找到 theta 函数？谢谢 ：）

Answer 1

O、Θ 和 Ω 表示法表示相关但非常不同的概念。O 表示法表示函数增长率的渐近上限；它说这个函数最终从上面被某个其他函数的某个常数倍数限制。Ω 表示法类似，但给出了一个下限。Θ 表示法给出了一个渐近的紧界——对于足够大的输入，算法的增长速度由函数的恒定倍数从上方和下方限定。

如果 f(n) = O(g(n))，则f(n) = Ω(g(n)) 或 f(n) = Θ(g(n)) 不一定为真。例如，1 = O(n)，但 1 ≠ Ω(n)，因为 n 的增长速度严格快于 1。

如果您发现 f(n) = O(g(n)) 和 Ω(h(n))，其中 g(n) ≠ h(n)，您可能需要进行更精确的分析以确定函数 j (n) 使得 f(n) = Θ(j(n))。如果 g(n) = Θ(h(n))，那么您可以得出 f(n) = Θ(g(n)) 的结论，但如果上限和下限不同，则无法确定 Θ函数的增长率。

希望这可以帮助！

Answer 2

f(n)=O(g(n)) 表示n>N => |f(n)|≤C|g(n)| 对于一些常数 N 和 C。

f(n)=Ω(g(n)) 表示n>N => |f(n)|≥C|g(n)| 对于一些常数 N 和 C。

f(n)=Θ(g(n)) 意味着 f(n)=O(g(n)) 和 f(n)=Ω(g(n))。

如果我们希望 g 成为“好”函数（例如 n^r*Log(n)^s 之类的函数），所有 f 都不可能找到 f(n)=Θ(g(n)) 的 ag . 例如，如果 f(n)=cos(n)²*n+sin(n)²*n²，我们有 f(n)=O(n²) 和 f(n)=Ω(n) 但我们可以t 找到一个“好”的 g 使得 f(n)=Θ(g(n))。