证明算法的Big-Oh时，找到C和N的简便方法是什么?

问题描述

我开始学习Big-Oh表示法.

I'm starting to learn about Big-Oh notation.

找到给定函数的C和N 的简便方法是什么?

What is an easy way for finding C and N for a given function?

例如，

(n + 1)或n + 5n + 10n + 5n + 1

(n+1), or n+5n+10n+5n+1

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

I know the formal definition for Big-Oh is:

我的问题是，选择c和N 的值的一种可靠的方法是什么?

My question is, what is a good, sure-fire method for picking values for c and N?

对于给定的(n + 1)多项式，我必须证明它是O(n ).因此，我应该如何选择c和N 以便使上面的定义正确而不用猜测?

For the given polynomial above (n+1), I have to show that it is O(n). So, how should I pick my c and N so that I can make the above definition true without guessing?

推荐答案

您可以通过将多项式中每个项的系数相加来选择常数c.自

You can pick a constant c by adding the coefficients of each term in your polynomial. Since

| n + 5n + 0n + 10n + 5n + 1n | < = | n + 5n + 0n + 10n + 5n + 1n |

| n + 5n + 0n + 10n + 5n + 1n | <= | n + 5n + 0n + 10n + 5n + 1n |

您可以简化双方以获得

| n + 5n + 10n + 5n +1 | < = | 22n |

| n + 5n + 10n + 5n + 1 | <= | 22n |

所以c = 22，并且对于任何n> = 1都将始终成立.

So c = 22, and this will always hold true for any n >= 1.

几乎总是可以通过提高N 来找到较低的c，但是这种方法有效，而且您可以在脑海中实现.

It's almost always possible to find a lower c by raising N, but this method works, and you can do it in your head.

(多项式周围的绝对值运算应考虑负系数.)

(The absolute value operations around the polynomials are to account for negative coefficients.)

这篇关于证明算法的Big-Oh时，找到C和N的简便方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！