相关疑难解决方法(0)

我开始学习Big-Oh符号了.

找到给定函数的C和N ₀的简单方法是什么？

比方说,例如:

(n + 1)⁵,或n ⁵ + 5n ⁴ + 10n ² + 5n + 1

我知道Big-Oh的正式定义是:

设f(n)和g(n)是将非负整数映射到实数的函数.我们说f(n)是O(g(n)),如果有一个实常数c> 0且整数常数N ₀ > = 1,那么每个整数N的f(n)<= cg(n)> N ₀.

我的问题是,为c和N ₀选择值的什么是一个好的,可靠的方法？

对于上面给定的多项式(n + 1)⁵,我必须证明它是O(n ⁵).那么,我应该如何选择我的c和N ₀以便我可以在不猜测的情况下使上述定义成立？

我正在修改 Big O 和其他相关边界的正式定义，有些事情让我感到困惑。在我正在阅读的书中 (Skiena) Big O 被定义为：

f(n) = O(g(n)) 当存在一个常数 c 使得 f(n) 对于某个 n > n0 的值总是 <= c*g(n)

这对我来说通常是有意义的。我们只关心足够大的 n 值，以至于增长率实际上很重要。但是为什么将 g(n) 乘以 c？似乎我可以为 c 选择一个非常大的值，并通过消除较小的 g(n) 值的大小来使整个事情变得随意。

辅助问题：选择将算法分类为复杂性类时，是拇指的一般规则，只需根据大O的定义选择仍然保存的最低增长类？根据定义，将恒定时间算法分类为 O(n!) 似乎是有效的，因为 f(n) 将 <= c*g(n)。当然，这没有任何价值。

谢谢！

我正在为我的Java III课阅读一本教科书.我们正在阅读关于Big-Oh的内容,我对其正式定义感到有些困惑.

形式定义:"函数f(n)最多为g(n) - 即f(n)= O(g(n)) - 如果存在正实数c和正整数N,则f (N)<= CG(n)的对所有的n> = N.也就是说,CG(n)是对F(N)当n是足够大的上界".

好的,这是有道理的.但坚持下去,继续阅读......这本书给了我这个例子:

"在段9.14中,我们说使用5n + 3操作的算法是O(n).我们现在可以通过使用Big Oh的形式定义来显示5n + 3 = O(n).

当n> = 3时,5n + 3 <= 5n + n = 6n.因此,如果我们让f(n)= 5n + 3,g(n)= n,c = 6,N = 3,我们已经证明了对于n> = 3,f(n)<= 6 g(n),或5n + 3 = O(n).也就是说,如果算法需要与5n + 3成正比的时间,则为O(n)."

好的,这种对我来说很有意义.他们说如果n = 3或更大,5n + 3比n小于3所花费的时间少 - 因此5n + n = 6n - 对吗？有意义,因为如果n是2,5 n + 3 = 13而6n = 12但是当n是3或更大时5n + 3总是小于或等于6n.

这是我感到困惑的地方.他们给我另一个例子:

例2:"让我们看一下4n ^ 2 + …

我正在学习这本书中的大O表示法。

大O表示法的定义是：

\n如果存在常数 C 和 k 使得 |f (x)| ，我们说 f (x) 是 O(g(x)) \xe2\x89\xa4 C|g(x)| 每当 x > k 时。\n

现在这是第一个例子：

\n示例 1 证明 f (x) = x^2 + 2x + 1 是 O(x^2)。
\n解：我们观察到，当 x > 1 时，我们可以很容易地估计 f (x) 的大小，因为 x 1。因此
\n0 \xe2\x89\xa4 x^2 + 2x + 1 \xe2\x89\xa4 x ^2 + 2x^2 + x^2 = 4x^2
\n只要 x > 1。因此，我们可以以 C = 4 和 k = 1 为证，证明 f …