2.1「Stanford Algorithms」The Gist

Well the question was the same and in this case the answer was the same so this algorithm just like the last one has running time big O of N if we actually count the number of operations it won't be exactly the ssame as last time it will be roughly twice as many operations.

As the previous piece of code.

That's because we have to search two different arrays, each of length n.

So whatever work we did before.

We now do it twice as many times.

Of course, that, too, being a constant independent of the input length n, is going to get suppressed once we passed a big O notation.

So, this, like the previous algorithm, is a linear time algorithm.

It has running time big O of n.

Let's look at a more interesting example of two loops where rather than processing each loop in sequence, they're going to be nested.

In particular let's look at the problem of searching whether two given input arrays each of length n contain a common number.

The code that we're going to look at for solving this problem is the most straightforward one you can, you can imagine where we just compare all possibilities.

So for each index i into the array a and each index j into the array b, we just see if A i is the same number as B j.

If it is, we return true.

If we exhaust all of the possibilities without ever finding equal elements Then we're save in returning false.

The question is of course is, in terms of big O notation, asymptotic analysis, as a function of the array length n, what is the running time of this piece of code?

好了，问题是相同的，在这种情况下，答案是相同的，因此，如果我们实际上计算操作次数，则该算法就像最后一个算法的运行时间大N为O一样，与上一次算法完全不同将大约是两倍的操作次数。

如上一段代码。

那是因为我们必须搜索两个不同的数组，每个数组的长度为n。

所以我们之前所做的任何工作。

现在，我们执行了两次。

当然，一旦我们通过一个大的O表示法，它也将不受输入长度n的影响而被抑制。

因此，与以前的算法一样，这是一个线性时间算法。

运行时间为n大。

让我们看一下两个循环的一个更有趣的示例，其中将嵌套它们，而不是按顺序处理每个循环。

特别地，让我们看一下搜索每个长度为n的两个给定输入数组是否包含一个公共数字的问题。

我们将要解决的代码是最简单的代码，您可以想象我们将所有可能性进行比较的地方。

因此，对于进入数组a的每个索引i和进入数组b的每个索引j，我们只看A i是否与B j相同。

如果是，则返回true。

如果我们在没有找到相等元素的情况下就用尽了所有可能性，那么我们将避免返回false。

问题当然是，就大的O表示法而言，渐近分析是作为数组长度n的函数，这段代码的运行时间是多少？