2.3「Stanford Algorithms」ASYMPTOT

Having slogged through the formal definition of big O notation, I wanna quickly turn to a couple of examples.

Now, I wanna warn you up front, these are pretty basic examples.

They're not really gonna provide us with any insight that we don't already have.

But they serve as a sanity check that the big O notation's doing what its intended purpose is.

Namely to supress constant factors and low order terms.

Obviously, these simple examples will also give us some, facility with the definition.

So the first example's going to be to prove formally the following claim.

The claim states that if T(n) is some polynomial of degree "k", so namely a<u>k n^k.

Plus all the way up to a<u>1 N + a<u>0.

For any integer "k", positive</u></u></u> integer "k" and any coefficients a<u>i's positive or negative.

Then: T(n) is big</u> O of n^k.

So this claim is a mathematical statement and something we'll be able to prove.

As far as, you know, what this claim is saying, it's just saying big O notation really does suppress constant factors and lower order terms.

If you have a polynomial then all you have to worry about is what is the highest power in that polynomial and that dominates its growth as "n" goes to infinity.

So, recall how one goes about showing that one function is big O of another.

The whole key is to find this pair of constants, c and n<u>0, where c quantifies the constant multiple</u> of the function you're trying to prove big O of, and n<u>0 quantifies what you mean</u> by "for all sufficiently large n.

" Now, for this proof, to keep things very simple to follow, but admittedly a little mysterious, I'm just gonna pull these constants, c and n<u>0, out of a hat.

So, I'm not gonna tell you how I derived them,</u> but it'll be easy to check that they work.

So let's work with the constants n<u>0</u> equal to one, so it's very simple choice of n<u>0 and then "c" we are gonna pick to</u> be sum of the absolute values of the coefficients.

So the absolute value of "a<u>k"</u> plus the absolute value of "a<u>(k-1)", and so on.

Remember I didn't assume that</u> the pol...

, the original polynomial, had non-negative coefficients.

So I claim these constants work, in the sense that we'll be able to prove to that, assert, you know, establish the definition of big O notation.

What does that mean? Well we need to show that for all "n" at least one (cause remember we chose n<u>0 equal to</u> one), T(n) (this polynomial up here) is bounded above by "c" times "n^k", where "c" is the way we chose it here, underlined in red.

So let's just check why this is true.

So, for every positive integer "n" at least one, what do we need to prove? We need to prove T(n) is upper bounded by something else.

So we're gonna start on the left hand side with T(n).

And now we need a sequence of upper bounds terminating with "c" times "n^k" (our choice of c underlined in red).

So T(n) is given as equal to this polynomial underlined in green.

So what happens when we replace each of the coefficients with the absolute value of that coefficient? Well, you take the absolute value of a number, either it stays the same as it was before, or it flips from negative to positive.

Now, "n" here, we know is at least one.

So if any coefficient flips from negative to positive, then the overall number only goes up.

So if we apply the absolute value of each of the coefficients we get an only bigger number.

So T(n) is bounded above by the new polynomial where the coefficients are the absolute values of those that we had before.

So why was that a useful step? Well now what we can do is we can play the same trick but with "n".

So it's sort of annoying how right now we have these different powers of "n".

It would be much nicer if we just had a common power of "n", so let's just replace all of these different "n"s by "n^k", the biggest power of "n" that shows up anywhere.

So if you replace each of these lower powers of "n" with the higher power "n^k", that number only goes up.

Now, the coefficients are all non negative so the overall number only goes up.

So this is bounded above by "the absolute value of a<u>k" "n^k"</u> ...

up to "absolute value of a<u>1" "n^k" ...

plus "a<u>0" "n^k".

</u></u> I'm using here that "n" is at least one, so higher powers of "n" are only bigger.

And now you'll notice this, by our choice of "c" underlined in red, this is exactly equal to "c" times "n^k".

And that's what we have to prove.

We have to prove that T(n) is at most "c" times "n^k", given our choice of "c" for every "n" at least one.

And we just proved that, so, end of proof.

Now there remains the question of how did I know what the correct, what a workable value of "c" and "n<u>0"</u> were? And if you yourself want to prove that something is big O of something else, usually what you do is you reverse engineer constants that work.

So you would go through a proof like this with a generic value of "c" and "n<u>0" and then</u> you'd say, "Ahh, well if only I choose "c" in this way, I can push the proof through.

" And that tells you what "c" you should use.

If you look at the optional video on further examples of asymptotic notation, you'll see some examples where we derive the constants via this reverse engineering method.

But now let's turn to a second example, or really I should say, a non-example.

So what we're going to prove now is that something is not big O of something else.

So I claim that for every "k" at least 1, "n^k" is not O(n^(k-1)).

And again, this is something you would certainly hope would be true.

If this was false, there'd be something wrong with our definition of big O notation and so really this is just to get further comfort with the definition, how to prove something is not big O of something else, and to verify that indeed you don't have any collapse of distinctive powers of ploynomials, which would be a bad thing.

So how would we prove that something is not big O of something else? The most...

frequently useful proof method is gonna be by contradiction.

So, remember, proof by contradiction, you assume what you're trying to, establish is actually false, and, from that, you do a sequence of logical steps, culminating in something which is just patently false, which contradicts basic axioms of mathematics, or of arithmetic.

So, suppose, in fact, n^k was big O of n^(k-1), so that's assuming the opposite of what we're trying to prove.

What would that mean? Well, we just referred to the definition of Big O notation.

If in fact "n^k" hypothetically were Big O of n^(k-1) then by definition there would be two constants, a winning strategy if you like, "c" and "n<u>0" such</u> that for all sufficiently large "n", we have a constant multiple "c" times "n^(k-1)" upper bounding "n^k".

So from this, we need to derive something which is patently false that will complete the proof.

And the way, the easiest way to do that is to cancel "n^(k-1)" from both sides of this inequality.

And remember since "n" is at least one and "k" is at least one, it's legitimate to cancel this "n^(k-1)" from both sides.

And when we do that we get the assertion that "n" is at most some constant "c" for all "n" at least "n<u>0".

And this now</u> is a patently false statement.

It is not the case that all positive integers are bounded above by a constant "c".

In particular, "c+1", or the integer right above that, is not bigger than "c".

So that provides the contradiction that shows that our original assumption that "n^k" is big O of "n^(k-1)" is false.

And that proves the claim.

"n^k" is not big O of "n^(k-1)", for every value of "k".

So different powers of polynomials do not collapse.

They really are distinct, with respect to big O notation.

在烦恼了大O表示法的正式定义之后，我想快速举几个例子。

现在，我想提前警告您，这些都是非常基本的示例。

他们并不会真正为我们提供我们尚未拥有的任何见解。

但是，它们用作健全性检查，以确保大O表示法是否能达到其预期目的。

即抑制常数因子和低阶项。

显然，这些简单的示例还将为我们提供一些定义方面的便利。

因此，第一个示例将正式证明以下权利要求。

该主张指出，如果T（n）是度为“ k”的某个多项式，则为a u kn ^ k。

一直加到a <u> 1 N + a <u> 0。

对于任何整数“ k”，为正数<u> </ u> </ u>整数“ k”以及任何系数a <u> i为正数或负数。

然后：T（n）是n ^ k的大O。

因此，此声明是一个数学陈述，我们将能够证明这一点。

就您所知，这种说法的意思是，大的O表示确实确实抑制了常数因子和低阶项。

如果您有一个多项式，那么您只需担心该多项式中的最高幂是多少，并且当“ n”趋于无穷大时，它便决定了它的增长。

因此，回想一下一个函数如何显示另一个函数的重要性。

整个关键是找到这对常数c和n <u> 0，其中c量化您要证明其大O的函数的常数倍</ u>，而n <u> 0量化什么您的意思是</ u>“对于所有足够大的n。

“现在，为了证明这一点，我想让事情变得很简单，但要承认有点神秘，我只是想把这些常数c和n <u> 0从帽子里拿出来。

因此，我不会告诉您我是如何衍生它们的，</ u>但要检查它们是否有效很容易。

因此，让我们使用常量n <u> 0 </ u>等于1的方法，因此非常简单地选择n <u> 0，然后选择“ c”作为绝对值之和</ u>的系数。

因此，“ a <u> k” </ u>的绝对值加上“ a <u>（k-1）”的绝对值，依此类推。

记住，我没想到</ u>

，原始多项式具有非负系数。

因此，我认为这些常量是有效的，在某种意义上说，我们可以证明这一点，断言，您可以确定大O表示法的定义。

这意味着什么？好吧，我们需要证明，对于所有“ n”，至少有一个（因为请记住，我们选择n <u> 0等于</ u>一个），T（n）（此处的多项式）的上界是“ c”乘以“ n ^ k”，其中“ c”是我们在此处选择的方式，用红色下划线标出。

因此，让我们检查一下为什么如此。

那么，对于每个正整数“ n”至少一个，我们需要证明什么？我们需要证明T（n）是其他事物的上限。

因此，我们将从T（n）的左侧开始。

现在我们需要一个以“ c”乘以“ n ^ k”终止的上界序列（我们选择的c用红色下划线标记）。

因此，T（n）等于绿色下划线的多项式。

那么，当我们用该系数的绝对值替换每个系数​​时会发生什么呢？好吧，您可以获取数字的绝对值，它可以保持与以前相同，或者从负数变为正数。

现在，这里的“ n”至少是一个。

因此，如果任何系数从负数变为正数，则总数只会增加。

因此，如果我们应用每个系数的绝对值，我们只会得到一个更大的数字。

因此，T（n）的上方是新多项式的边界，其中系数是我们之前拥有的绝对值。

那么，为什么这是一个有用的步骤呢？好了，现在我们可以做的是，我们可以玩同样的把戏，但是要用“ n”。

因此，现在我们具有这些不同的“ n”次幂有点令人讨厌。

如果我们仅拥有一个公用的“ n”幂，那就更好了，所以让我们用“ n ^ k”替换所有这些不同的“ n”，n的最大幂出现在任何地方。

因此，如果用较高的功率“ n ^ k”替换这些较低的功率“ n”，则该数字只会增加。

现在，系数都是非负的，因此总数只会增加。

因此，这在上面受“ a <u> k的绝对值”“ n ^ k” </ u>的限制...

直到“ a <u> 1的绝对值”“ n ^ k” ...

加“ a <u> 0”“ n ^ k”。

</ u> </ u>我在这里使用的是“ n”至少一个，因此“ n”的高次幂只会更大。

现在，您会注意到这一点，通过选择带红色下划线的“ c”，它等于“ c”乘以“ n ^ k”。

这就是我们必须证明的。

考虑到我们为至少每个“ n”选择“ c”，我们必须证明T（n）最多是“ c”乘以“ n ^ k”。

我们只是证明了证明的终结。

现在还有一个问题，我如何知道正确的值，“ c”和“ n <u> 0” </ u>的可行值是多少？而且，如果您自己想证明某事物是其他事物的大本营，那么通常您要做的就是反向工作的工程师常数。

因此，您将使用通用值“ c”和“ n <u> 0”进行这样的证明，然后</ u>您会说：“啊，好吧，只要我这样选择“ c” ，我可以通过证明。

”，这告诉您应该使用什么“ c”。

如果您观看有关渐近符号的其他示例的可选视频，则会看到一些示例，这些示例中我们通过这种逆向工程方法得出常数。

但是，现在让我们转到第二个例子，或者说不真实的例子。

因此，我们现在要证明的是，其他事物并不重要。

所以我声称对于每个“ k”至少为1，“ n ^ k”不是O（n ^（k-1））。

再说一遍，您肯定希望这是对的。

如果这是错误的，那么我们对大O表示法的定义就会出现问题，因此，这实际上只是为了进一步简化该定义，如何证明某物不是其他大O，并验证您确实没有任何独特的ploynomial权力崩溃，那将是一件坏事。

那么，我们如何证明某物不是其他物的大O？最多...

经常有用的证明方法将是矛盾的。

因此，请记住，以矛盾为依据，您假设您要尝试建立的东西实际上是错误的，然后，您执行了一系列逻辑步骤，最终达到了某些显然是错误的事实，这与数学的基本公理相矛盾。 ，或算术。

因此，实际上，假设n ^ k是n ^（k-1）的大O，因此这与我们试图证明的事实相反。

那是什么意思？好吧，我们只是提到了Big O符号的定义。

如果实际上假设“ n ^ k”是n ^（k-1）的Big O，那么根据定义，它将有两个常数，如果您愿意，则为获胜策略，例如“ c”和“ n <u> 0” </ u>对于所有足够大的“ n”，我们有一个恒定的“ c”乘以“ n ^（k-1）”上限“ n ^ k”。

因此，我们需要从中得出明显错误的信息，以完成证明。

而且，最简单的方法是从该不等式的两端消除“ n ^（k-1）”。

并且请记住，由于“ n”至少为一个，而“ k”至少为一个，因此从两侧取消此“ n ^（k-1）”是合法的。

并且当我们这样做时，我们得到断言，对于所有“ n”，至少“ n <u> 0”，“ n”至多是一个常数“ c”。

现在，这</ u>显然是虚假的陈述。

不是所有的正整数都由常数“ c”限制在上面。

特别地，“ c + 1”或其正上方的整数不大于“ c”。

因此，这提供了一个矛盾，表明我们最初的假设“ n ^ k”是“ n ^（k-1）”的大O是错误的。

这证明了要求。

对于“ k”的每个值，“ n ^ k”都不是“ n ^（k-1）”的大O。

因此，多项式的不同幂不会崩溃。

就大的O表示法而言，它们确实是截然不同的。