2.1「Stanford Algorithms」The Gist

In this sequence of lectures we're going to learn Asymptotic Analysis.

This is the language by which every serious computer programmer and computer scientist discusses the high level performance of computer algorithms.

As such, it's a totally crucial topic.

In this video, the plan is to segue between the high level discussion you've already seen in the course introduction and the mathematical formalism,which we're going to start developing in the next video.

Before getting into that mathematical formalism, however.

I want to make sure that the topic is well motivated.

That you have solid intuition for what it's trying to accomplish.

And also that you've seen a couple simple, intuitive examples.

Let's get started.

[UNKNOWN] analysis provides basic vocabulary for discussing the design and analysis in algorithms.

More, it is a mathematical concept it is by no means math for maths sake.

You will very frequently hear serious programmers saying that such and such code runs at O of n time, where such and such other code runs in o of n square times.

It's important you know what programmers mean when they make statements like that.

The reason this vocabulary is so ubiquitous, is that it identifies a sweet spot for discussing the high level performance of algorithms.

What I mean by that is, it is on the one hand coarse enough to suppress all of the details that you want to ignore.

Details that depend on the choice of architecture, the choice of programming language, the choice of compiler.

And so on.

On the other hand, it's sharp enough to be useful.

In particular, to make predictive comparisons between different high level algorithmic approaches to solving a common problem.

This is going to be especially true for large inputs.

And remember as we discussed in some sense.

Large inputs are the interesting ones.

Those are the ones for which we need algorithmic enginuity.

For example, asotonic analysis will allow us to differentiate between better and worse approaches to sorting.

Better and worse approaches to multiplying two integers, and so on.

Now most serious programmers if you ask them, what's the deal with asymptotic analysis anyways? They'll tell you reasonably, that the main point is to suppress both leading constant factors and lower order terms.

Now as we'll see there's more to Asymptotic Analysis than just these seven words here but long term, ten years from now, if you only remember seven words about Asymptotic Analysis I'll be reasonably happy if these are the seven words that you remember.

So how do we justify adopting a formalism which essentially by definition suppresses constant factors and lower-order terms.

Well lower-order terms basically by definition become increasingly irrelevant as you focus on large inputs.

Which as we've argued are the interesting inputs, the ones where algorithmic ingenuity is important.

As far as constant factors these are going to be highly dependent on the details of the environment, the compiler, the language and so on.

So, if we want to ignore those details it makes sense to have a formalism which doesn't focus unduly on leading constant factors.

Here's an example.

Remember when we analyzed the merge sort algorithm? We gave an upper bound on its running time that was 6 times n log n plus 6n where n was the input length, the number of numbers [COUGH] in the input array.

So, the lower order term here is the 6n.

That's growing more slowly than n log n.

So, we just drop that.

And then the leading constant factor is the 6 so we supress that well after the 2 supressions we're left with a much simpler expression N log N.

The terminology would then be to say that the running time of merge search is big O of N log N.

So in other words when you say that an algorithms is big O of some function what you mean is that after you drop the lower order terms.

And suppress the leasing, leading constant factor, you're left with the function f of n.

Intuitively that is what big O notation means.

So to be clear I'm certainly not asserting the constant factors never matter when you're designing an alg, analyzing algorithms.

Rather, I'm just saying that when you think about high-level algorithmic approaches, when you want to make a comparison between fundamentally differnt ways of solving a problem.

Asymptotic Analysis is often the right tool for giving you guidance about which one is going to perform better, especially on reasonably large inputs.

Now, once you've committed to a particular algorithmic solution to a problem Of course, you might want to then work harder to improve the leading constant factor, perhaps even to improve the lower order terms.

By all means, if the future of your start-up depends on how efficiently you implement some particular set of lines of code, have at it.

Make it as fast as you can.

In the rest of this video I want to go through four very simple examples.

In fact, these examples are so simple, if you have any experience with big O notation You're probably just better off skipping the rest of this video and moving on the mathematical formalism that we begin in the next video.

But if you've never seen it before I hope these simple examples will get you oriented.

So let's begin with a very basic problem, searching an array for a given integer.

Let's analyze the straight forward algorithm for this problem where we just do a linear scan through, through the array, checking each entry to see if it is the desired integer t.

That is the code just checks each array entry in turn.

If it ever finds integer t it returns true.

If it falls off the end of the array without finding it it returns false.

So, what do you think? We haven't formally defined big O notation but, I've given you an intuitive description.

What would you say is the running time of this algorithm as a function of the length of the array of capital A.

在这一系列的讲座中，我们将学习渐近分析。

这是每位认真的计算机程序员和计算机科学家用来讨论计算机算法高水平性能的语言。

因此，这是一个至关重要的话题。

在此视频中，计划是在课程介绍中已经看到的高级讨论与数学形式主义之间进行区分，我们将在下一个视频中开始进行开发。

但是，在进入那种数学形式主义之前。

我想确保该主题的动机良好。

您对它要完成的工作具有扎实的直觉。

而且您已经看到了几个简单，直观的示例。

让我们开始吧。

[未知]分析为讨论算法中的设计和分析提供了基本词汇。

而且，这是一个数学概念，从数学上来说绝对不是数学。

您会经常听到严肃的程序员说这样的代码在n倍的O中运行，而其他的代码在n平方倍的o中运行。

重要的是，要知道程序员做出这样的声明时意味着什么。

该词汇表无处不在的原因是，它为讨论算法的高级性能确定了一个最佳位置。

我的意思是，一方面，它足够粗略，可以隐藏您要忽略的所有细节。

详细信息取决于体系结构的选择，编程语言的选择，编译器的选择。

等等。

另一方面，它足够有用。

尤其是要在解决高级问题的不同高级算法方法之间进行预测比较。

对于大型输入，尤其如此。

并记住我们在某种意义上进行的讨论。

大量的输入是有趣的。

这些是我们需要算法上的能力的。

例如，等渗分析将使我们能够区分更好和更差的分类方法。

乘以两个整数的更好和更差的方法，依此类推。

现在，如果您问大多数最认真的程序员，那么渐近分析又有什么用呢？他们会合理地告诉您，重点是同时抑制前导常数因子和低阶项。

现在，我们将看到渐进分析的功能远不止这七个词，但从十年以后的长期来看，如果您只记得有关渐进分析的七个词，那么我会很高兴的是，如果您记住这七个词。

因此，我们如何证明采用形式主义是合理的，该形式主义本质上通过定义抑制了常数因子和低阶项。

从本质上讲，当您专注于大型输入时，低级术语变得越来越不相关了。

正如我们所争论的是有趣的输入，其中算法的独创性很重要。

就恒定因素而言，这些因素将高度依赖于环境的详细信息，编译器，语言等。

因此，如果我们想忽略那些细节，那么采取形式主义而不是过分关注主导因素是有意义的。

这是一个例子。

还记得我们分析合并排序算法时的情况吗？我们给出了其运行时间的上限，即上限为n log n的6倍加6n，其中n为输入长度，即输入数组中的数字[COUGH]。

因此，这里的低阶项是6n。

它的增长速度比n log n慢。

因此，我们将其删除。

然后领先的常数因子是6，因此我们抑制了2个抑制之后，我们留下了一个简单得多的表达式N logN。

然后，用术语说合并搜索的运行时间为N log N的大O。

因此，换句话说，当您说算法对某些功能来说是很大的O时，您的意思是删除低阶项之后。

并抑制租赁的前导常数因子，您将得到n的函数f。

直观地讲，这就是大O表示的意思。

因此，要明确一点，当您设计算法，分析算法时，我当然不会断言常数因子永远都没有关系。

相反，我只是说，当您考虑高级算法方法时，当您想在解决问题的根本不同方法之间进行比较时。

渐近分析通常是正确的工具，可为您提供指导，使您可以更好地执行哪一项，尤其是在相当大的输入上。

现在，一旦您致力于针对问题的特定算法解决方案，当然，您可能希望然后更加努力地改善前导常数因子，甚至可能改善低阶项。

不管怎样，如果您创业的未来取决于实现某些特定代码行的效率，那就可以了。

使其尽可能快。

在本视频的其余部分中，我想介绍四个非常简单的示例。

实际上，这些示例非常简单，如果您有使用大O表示法的经验，那么最好跳过该视频的其余部分，继续我们在下一个视频中开始的数学形式主义。

但是，如果您从未见过，希望这些简单的例子能使您适应。

因此，让我们从一个非常基本的问题开始，在数组中搜索给定的整数。

让我们分析该问题的简单算法，在该算法中，我们通过数组进行线性扫描，检查每个条目以查看它是否为所需的整数t。

那就是代码只是依次检查每个数组条目。

如果找到整数t，则返回true。

如果它从数组末尾掉落却找不到，它将返回false。

所以你怎么看？我们尚未正式定义大O符号，但是，我给了您一个直观的描述。

您要说的是，此算法的运行时间是大写字母A数组长度的函数。