algorithm - 顺序符号中函数的最大值和最小值

Question

Order notation question, big-o notation and like:

函数的最大值和最小值在阶数表示法中的含义是什么？

例如:

DEFINITION:

"Maximum" rules: Suppose that f(n) and g(n) are positive functions for all n > n₀.

Then:

• O[f(n) + g(n)] = O[max (f(n),g(n)) ]

• etc...

我需要使用这些定义来证明一些家庭作业..感谢您的帮助!

编辑:f(n) 和 g(n) 应该表示算法相对于输入大小的运行时间

Answer 1

使用 Big-O 表示法，您谈论的是计算的上限。这意味着您只对组合函数的最大 项感兴趣，因为n(变量)趋于无穷大。此外，您还可以删除任何常量乘数，因为符号的正式定义允许您丢弃这些部分，这一点很重要，因为它可以让您专注于算法的行为而不是算法的实现。

因此，我们通过求和来组合两个函数。嗯，有两种情况(严格来说是三种，但它是对称的):

1. 一个函数的阶数高于另一个。在这一点上，高阶函数占主导地位；你可以假装较小者不存在。
2. 两个函数的顺序相同。这就像你正在对两者进行某种比率求和(因为我们已经丢弃了比例因子)但是你最终得到的是相同的因子并且只是稍微改变了比例因子。

最终结果看起来非常像 max() 函数，尽管它实际上不是(它实际上是 max 在函数空间上的泛化)，因此使用该符号非常方便。