2.1「Stanford Algorithms」The Gist

So this time, the answer has changed.

For this piece of code, the running time is not big O of n.

But it is big O of n squared.

So we might also call this a quadratic time algorithm.

because the running time is quadratic in the input length n.

So this is one of those kinds of algorithms, where, if you double the input length.

Then the running time of the algorithm will go up by a factor of 4, rather than by a factor of 2 like in the previous two pieces of code.

So, why is this? Why does it have [UNKNOWN] running time [UNKNOWN] of n squared? Well again, there's some constant setup cost which gets suppressed in the big [UNKNOWN].

Again, for each fixed choice of an entry i into array a, and then index j for array b for each fixed choice for inj.

We only do a constant number of operations.

The particular constants are relevant, because it gets suppressed in the big O notation.

What's different is that there's a total of n squared iterations of this double four loop.

In the first example, we only had n iterations of a single four loop.

In our second example, because one four loop completed before the second one began.

We had only two n iterations overall.

Here for each of the n iterations of the outer for loop we do n iterations of the inner for loop.

So that gives us the n times n i.e. n squared total iterations.

So that's going to be the running time of this piece of code.

Let's wrap up with one final example.

It will again be nested for loops, but this time, we're going to be looking for duplicates in a single array A, rather than needing to compare two distinct arrays A and B.

So, here's the piece of code we're going to analyze for solving this problem, for detecting whether or not the input array A has duplicate entries.

There's only 2 small difference relative to the code we went through on the previous slide when we had 2 different arrays the first surprise, the first change won't surprise you at all which instead of referencing the array B I change that B to an A so I just compare the ith entry of a to the Jth entry of A.

The second change is a little more subtle which is I changed the inner for loop so the index J begins.

At I plus 1.

Where I is the current value of the outer four loops index.

Rather than starting at the index 1.

I could have had it start at the index one.

That would still be correct.

But, it would be wasteful.

And you should think about why.

If we started the inner four loops index at 1.

Then this code would actually compare each distinct pair of elements at a to each other twice.

Which, of course, is silly.

You only need to compare two different elements of a to each other one.

To know whether they are equal or not.

So this is the piece of code.

The question is the same as it always is what in terms of bigger notations in the input link n is the running time of this piece of code.

所以这次，答案已经改变。

对于这段代码，运行时间不是n的大O。

但这是n平方的大O。

因此，我们也可以将其称为二次时间算法。

因为在输入长度n中运行时间是平方的。

因此，这是这类算法之一，在这种情况下，如果将输入长度加倍。

然后，算法的运行时间将增加4倍，而不是前两段代码中的2倍。

那么，为什么呢？为什么[UNKNOWN]运行时间[UNKNOWN]为n平方？再说一遍，有一些固定的设置成本在大型[未知]中得到了抑制。

同样，对于数组i中条目i的每个固定选择，然后针对inj的每个固定选择，为数组b索引j。

我们只进行固定数量的操作。

特定的常数是相关的，因为它以大O表示法被抑制。

不同之处在于，此双四循环总共进行n次平方迭代。

在第一个示例中，我们只有一个四个循环的n次迭代。

在我们的第二个示例中，因为一个四循环在第二个循环开始之前完成。

我们总共只有两次n次迭代。

在这里，对于外部for循环的n次迭代中的每一个，我们对内部for循环进行n次迭代。

这样就给了我们n倍n即n个平方的总迭代次数。

这就是这段代码的运行时间。

让我们结束一个最后的例子。

它将再次嵌套用于循环，但是这一次，我们将在单个数组A中寻找重复项，而不是需要比较两个不同的数组A和B。

因此，这是我们要分析的代码段，用于解决此问题，检测输入数组A是否具有重复项。

当我们有2个不同的数组时，与上一张幻灯片中的代码相比，只有2个细微的差别，第一个惊喜，第一个更改完全不会令您惊讶，而不是将数组BI的更改从B引用为A，所以我只是比较a的第i个条目和A的第j个条目。

第二个更改有些微妙，这是我更改了内部for循环，从而使索引J开始。

在我加1。

其中，I是外部四个循环索引的当前值。

而不是从索引1开始。

我本来可以从索引1开始的。

那仍然是正确的。

但是，这将是浪费。

您应该考虑为什么。

如果我们从1开始内部的四个循环索引。

然后，此代码实际上会将a处的每个不同的元素对彼此进行两次比较。

当然，这是愚蠢的。

您只需要将a的两个不同元素相互比较。

要知道它们是否相等。

所以这是一段代码。

问题始终是相同的，就输入链接中更大的表示法而言，n是这段代码的运行时间。