2.1「Stanford Algorithms」The Gist

So the answer to this question, same as the last one.

Big O of n squared.

That is, this piece of code is also a quad-, has quadratic running time.

So what I hope was clear was that, you know? Whatever the running time of this piece of code is.

It's proportional to the number of iterations of this double four loop.

Like in all the examples, we do constant work per iteration.

We don't care about the constant.

It gets suppressed by the big O notation.

So, all we gotta do is figure out how many iterations there are of this double four loop.

My claim is that there's roughly n squared over two iterations of this double four loop.

There's a couple ways to see that.

Informally, we discussed how the difference between this code and the previous one, is that, instead of counting something twice, we're counting it once.

So that saves us a factor of two in the number of iterations.

Of course, this one half factor gets suppressed by the big O notation anyways.

So the big O, running time doesn't change.

A different argument would just say, you know? How many, there's one iteration for every distinct choice of i and j of indices between one and n.

And a simple counting argument.

Says that there's n choose 2 such choices of distinct i and j, where n choose 2 is the number n times n minus 1 over 2.

And again, supressing lower-order terms and the constant factor, we still get a quadratic dependence on the length of the input array A.

So that wraps up some of the sort of just simple basic examples.

I hope this gets you oriented, you have a strong intuitive sense for what big O notation is trying to accomplish.

And how it's defined mathematically.

Let's now move onto both the mathematical developments and some more interesting algorithms.

因此，这个问题的答案与上一个相同。

n的大O平方。

也就是说，这段代码也是四倍的，具有二次运行时间。

所以我希望清楚的是，您知道吗？无论这段代码的运行时间如何。

它与这个双四循环的迭代次数成正比。

像所有示例一样，我们在每次迭代中都做不断的工作。

我们不在乎常量。

大号O表示抑制了它。

因此，我们要做的就是找出这个双四循环的迭代次数。

我的主张是在这个双四循环的两次迭代中大约有n平方。

有几种方法可以看到这一点。

非正式地，我们讨论了此代码与上一个代码之间的区别是，我们没有计算两次，而是计算了一次。

这样可以为我们节省两倍的迭代次数。

当然，无论如何，这一二分之一因素会被大的O表示法抑制。

因此，大O，运行时间不会改变。

一个不同的论点只会说，你知道吗？多少，索引i和j在n和n之间的每个不同选择都有一个迭代。

还有一个简单的计数论点。

假设有n个选择这样的i和j的2个选择，其中n选择2是n乘以n减去1等于2的数字。

再次，抑制低阶项和常数因子，我们仍然对输入数组A的长度有二次依赖性。

这样就构成了一些简单的基本示例。

我希望这能使您有方向，对大型O标记试图完成的工作具有强烈的直觉感。

以及如何对其进行数学定义。

现在，让我们继续进行数学开发和一些更有趣的算法。