2.1「Stanford Algorithms」The Gist

So the answer I am looking for is C, the O(n) or covalently we would say that the running time of this algorithm is linear in the input length n.

Why is that true? Well, let's think about how many operations this piece of code is going to execute.

Actually, the lines of code executed is going to depend on the input.

It depends on whether or not the target t is contained in the array a, and if so, where in the array a it lies.

But, in the worse case, this code will do an unsuccessful search.

>> T will not be in the array and the code will scan through the entire array A and return false.

The number of operations then is a constant.

There's some initial setup perhaps and maybe it's an operation to return this final boolean value, but outside of that constant which will get suppressed in the big annotation, it does a constant number of operations per entry in the array.

And you could argue about what the constant is, if it's 2, 3, 4 operations per entry in the array, but the point it whatever that constant is, 2, 3, or 4, it gets conveniently suppressed by the Big O notation.

So as a result, total number of operations will be linear in n, and so the Big O notation will just be O of N.

So that was the first example, and the last three examples, I want to look at different ways that we could have two loops.

And in this example, I want to think about one loop followed by another.

So two loops in sequence.

I want to study almost the same problem as the previous one.

Where now we're just given two arrays, capital a and capital b, we'll say both of the same length n, and we want to know whether the target t is in either one of them.

Again, we'll look at the straightforward algorithm, where we just search through A, and if we fail to find t in A, we search through B.

If we don't find t in B either, then we have to return false.

So the question then is exactly the same as last time.

Given this new longer piece of code, what, in big O notation, is its running time?

因此，我要寻找的答案是C，O（n），或者说我们共价地说，该算法的运行时间在输入长度n中是线性的。

为什么会这样呢？好吧，让我们考虑一下这段代码要执行多少个操作。

实际上，执行的代码行将取决于输入。

这取决于目标t是否包含在数组a中，如果包含，则取决于它在数组a中的位置。

但是，在最坏的情况下，此代码将无法成功搜索。

>> T将不在数组中，并且代码将扫描整个数组A并返回false。

这样，操作数是一个常数。

可能有一些初始设置，也许是返回该最终布尔值的操作，但是在该常量之外（该常量将在大注释中被抑制）之外，它对数组中的每个条目执行恒定数量的操作。

您可以争论一下什么是常数，如果它是数组中每个条目的2、3、4个运算，但是无论该常数是2、3还是4，指向它的点都可以通过Big O表示法方便地抑制。

因此，运算的总数将在n中呈线性，因此Big O表示法将仅是N中的O。

所以这是第一个示例，最后三个示例，我想看看可以有两个循环的不同方式。

在此示例中，我想考虑一个循环，然后是另一个循环。

所以依次有两个循环。

我想研究与上一个几乎相同的问题。

现在仅给出两个数组，大写字母a和大写字母b，我们将说它们的长度n相同，并且我们想知道目标t是否在两个数组中的任何一个中。

再次，我们将看一下简单的算法，即只搜索A，如果我们在A中找不到t，则搜索B。

如果我们在B中也找不到t，则必须返回false。

因此，问题与上次完全相同。

给出了这段较长的新代码，用大O表示，它的运行时间是多少？