ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

大写O符号 – 译学馆
未登陆,请登陆后再发表信息
最新评论 (0)
播放视频

大写O符号

Big O Notation

嗨 我是盖尔·拉克曼·麦克道尔
Hi, I’m Gayle Laakmann McDowell,
《程序员面试金典》作者
author of Cracking the Coding Interview.
今天讲我最喜欢的话题之一 大O符号 或算法效率
Today we’ll cover one of my favorite topics, which is big O, or algorithmic efficiency.
先从一个故事说起
I’m going to start off with a story.
回到2009年 南非有一家公司
Back in 2009 there was this company in South Africa
他们的网络实在很慢
and they had really slow internet
因而他们感到非常沮丧
they were really really frustrated by,
实际上他们有两间相距50英里的办公室
and they actually had two offices about 50 miles away,
于是他们就做了一个小测试
so they set up this little test
来看看传输大量数据时
to see if it would be faster to transfer big chunks of data
是通过他们巨慢的网络服务商的网络
over the internet with their really slow internet service provider
还是通过信鸽更快
or via carrier pigeon.
他们把一捆USB棒 也或许是一个
Literally they took a bunch of USB sticks or
超大的USB棒绑到一只信鸽身上
probably actually one giant one strapped it to a pigeon
让它从一间办公室飞向另一间
and flew it from one office to the next,
他们为这个测试招来了大量的新闻报社
and they got a ton of press over this test
媒体大多热衷于此类事情
and media kind of love this stuff right.
当然 信鸽赢了
And of course the pigeon won,
否则这故事便算不上有趣
right it wouldn’t be a funny story otherwise.
他们招来了大量的新闻报社
And so they got a whole bunch of press over,
人们对此非常惊讶
and people are like oh my god
不敢相信一只信鸽打败了网络
I can’t believe that a pigeon beat the internet.
但问题是 这个测试其实有点荒唐可笑
But the problem was it was really actually kind of a ridiculous test
因为
because here’s the thing.
通过网络传输数据时
Transferring data over the Internet
所需时间随着数据量增长而变得越来越长
takes longer and longer and longer with how much data there is.
出于某些简化和假设
With certain simplifications and assumptions,
信鸽的情况并非那样
that’s not really the case with pigeons.
信鸽速度可能很快或者很慢
Pigeons might be really slow or fast
但它在两间办公室间传输一堆数据
but it always basically takes the same amount of time for a pigeon to transfer one,
所花时间基本相同
transfer some chunk of data from one office to the next.
它只需要飞50英里
It just has to fly 50 miles.
无需更远
It’s not going to take longer
因为USB棒包含更多数据
because that USB stick contains more data,
数据量够大时信鸽当然会赢
so of course for a sufficiently large file the pigeon’s going to win.
在大O符号里 我们对此的说法是
So in big O, the way we talk about this is
我们把信鸽传输速度描述为O(1)
we describe the pigeon transfer speed as O of 1,
相对于输入量 所需时间都是恒定的
it’s constant time with respect to the size of the input.
不会随着输入增加而增加
It doesn’t take longer with more input.
再次说明 这个结果是基于对信鸽运输
Again with certain simplifications and assumptions
usb棒能力的简化和假设
about the pigeons ability to carry a USB stick.
但网络传输时间是O(n)的
But the internet time is internet transfer time is O of n.
它相对于输入量呈线性增长
It scales linearly with respect to the amount of input.
两倍数据量大约需要两倍时间
Twice amount of data is going to take roughly twice as much time.
这就是大O的含义
So that’s what Big O is.
大O本质上是一个描述
Big O is essentially an equation that describes
运行时间怎样随着输入变量而变化的方程式
how the runtime scales with respect to some input variables.
我会讲到四个特定的准则
So I’m going to talk about four specific rules,
但先来看看它在代码里的样子
but first let me show you what this might look like in code.
考虑这个简单的函数
So let’s consider this simple function
它遍历一个数组并检查
that just walks through an array and checks if
数组是否包含一个特定值
it contains a particular value.
你会把这个函数描述为O(n)
So you would describe this is O of n,
n为数组长度
where n is the size of the array.
那这个遍历数组并打印
What about this method that walks through an array
其中所有成对值的函数呢
and prints all pairs of values in the array?
注意 如果2 5都在数组里
Note that this will print if it has the elements 5 and 2 in the array
它会同时打印(2,5)和(5,2)
it’ll print both 2 comma 5 and 5 comma 2.
你可以把它描述为O(n²)
So you describe this probably as of O of n squared
n为数组长度
and where n is the size of the array.
因为数组里有n个元素
You can see that because it has n elements in the array,
所以它就有n²个成对值
so it has n squared pairs,
函数所需的运行时间
so the amount of time it’s going to take you to run that
相对于n²而增长
function is going to increase with respect to n squared.
这就是大O的基本知识
Ok so that’s kind of basics of Big O.
来看另一个现实中的例子
Let’s take another real-world example.
怎样描述收割一块正方形土地所需时间?
How would you describe the run time to mow a square plot of land?
一块正方形草场 要全部收割完
So a square plot of grass. So you have this plot of grass and you need to mow all of it.
需要多少运行时间?
What’s the runtime of this?
这是一个有趣的问题
Well it’s kind of an interesting question,
你可以用两种方法来描述它
but you could describe it one of two ways.
一种方法是把它描述为O(a)
One of which, one way you can describe it is O of a
a为土地面积
where a is the amount of area in that plot of land.
记住 它只是一个描述
Remember that this is just an equation that
时间如何增长的方程式
expresses how the time increases
你并不一定要在方程式里使用n
so you don’t have to use n in your equation,
你能使用其它变量
you can use other variables
通常这都是可以的
and often it make sense to do that.
你可以把它描述为O(a)
So you just described this as O of a
a为正方形区域面积
where a is that the amount of area there.
你还可以把它描述为O(s²)
You could also describe this as O of s squared
s为正方形的边长
where s is the amount of, is this length of one side,
因为正方形面积a就等于边长s的平方
because it is a square plot of land so the amount of area is s squared.
所以重要的是你知道O(a)
So it’s important that you realize that there’s O of a,
和O(s²)本质上说的是一样的
and O of s squared are obviously saying essentially the same thing,
就像你在描述一个正方形那样
just like when you describe the area of a square.
你可以说它是25或5²
Well you could describe it as 25 or you describe it as 5 squared,
因为里面有一个正方形也不会让它变大
just because it has a square in it doesn’t make it bigger.
所以两种描述方法都行
So both are valid ways of describing the runtime.
取决于哪种能把问题说得更清楚
It just depends on what might be clearer for that problem.
接着讲大O的四个重要准则
So with that said, let me go on to 4 important rules to know with the big O.
第一 如果在算法里有两个不同步骤
The first one is if you have two different steps in your algorithm,
你就把这些步骤加起来
you add up those steps,
假如第一步所需时间为O(a)
so if you have a first step that takes O of a time
第二步所需时间为O(b)
and a second step that takes O of b
将这些运行时间相加就得到O(a+b)
you would add up those run times and you get O of a plus b.
例如 有一个算法
So for example you have this runtime that, you have this algorithm,
它遍历一个数组 接着又遍历另一个数组
that first walks through one array, and then it walks the other array.
所需时间就是分别遍历两者之和
It’s going to be the amount of time it takes to walk through each of them.
所以把它们的运行时间相加
So you’ll add up their runtimes.
第二个准则是舍去常量
The second way, the second rule is that you drop constants.
我们来看看打印数组里
So let’s look at these two different ways
最大最小值的两种不同方法
that you can print out the min and max element in an array.
一个先找最小值再找最大值
One finds the min element and then finds the max element,
另一个同时寻找最大最小值
the other one finds the min and the max simultaneously.
现在它们基本上做的是相同的事情
Now these are fundamentally doing the same thing,
它们的操作本质上完全相同
they’re doing essentially the exact same operations,
只是顺序上稍微不同
just doing them in slightly different orders.
它们都被描述为O(n)
Both of these get described as O of n,
n为数组长度
where n is the size of the array.
现在人们看到两个不同循环就
Now it’s really tempting for people to sometimes see two
很容易误以为它是O(2n)
different loops and describe it as O of 2n
因此重要的是记得在大O里要舍去常量
and so it’s important that you remember that you drop constants in big O.
就不会错认为是O(2n)或O(3n)
You do not describe things as O of 2n or O of 3n
因为你只是大略的比例
because you’re just looking for how things scale roughly.
看它是不是线性的 是不是平方的
Is it a linear relationship, is it a quadratic relationship,
所以总是要舍去常量
so you always drop constants.
第三个准则 如果有不同的输入
The third rule is that if you have different inputs
通常就要用不同的变量来表示它们
you’re usually going to use different variables to represent them.
来看看这个例子 有两个数组
So let’s take this example where we have two arrays
我们要遍历这两个数组并求出
and we’re walking through them to figure out the number of elements
两个数组里的相同元素的数量
in common between the two arrays.
一些人错认为它是O(n²)但并不正确
Some people mistakenly call this O of n squared but that’s not correct.
当谈到运行时间 如果你说它是O(n)
When you just talk about runtime if you describe things as
或O(n²) 或O(n*log n)
O of n or O of n squared or O of n log n,
n必须要有一个意义
n must have a meaning,
它并不像某种固有的东西
it’s not like things are inherently one or other.
当你说它是O(n²)时 那真的没有意义
So when you described this as O of n squared it really doesn’t make sense
因为……n表示什么?假如有两个不同的数组
because it doesn’t, what does n mean? n is not the
n也不是数组长度
size of the array, if there’s two different arrays.
相反你应该把它描述为O(a*b)
What you want to describe instead is O of a times b.
另外大O基本是一个表示
Again fundamentally, big O is an equation that
运行时间如何变化 以何种比例增加的方程式
expresses how the runtime changes, how its scales,
所以把它描述为O(a*b)
so you describe this as O of a times b.
第四准则 舍去次要因素
The fourth rule is that you drop non-dominant terms.
假设这是你的代码
So let’s suppose you have this code here
它遍历一个数组并打印最大元素
that walks through an array and prints out the biggest element
接着它继续打印数组中所有成对值
and then for some reason it goes and prints all pairs of values in the array.
第一步时间是O(n)
So that first step takes O of n time,
第二步时间是O(n²)
the second step takes O of n squared time,
首先可以采用更简化的形式
so you could first get as a less simplified form,
把它写成O(n+n²)
you could describe this as O of n + n squared,
但要注意 它与O(n)或
but note that, compare this to O of n
与n²的运行时间以及
and the runtime, or compare this to the runtime of n squared,
n²+n²的运行时间相比
and the runtime of n squared plus n squared.
这两个的运行时间都递减到n²
Both of those two runtimes reduce down to n squared
有趣的是 逻辑上
and what’s interesting here is that
O(n+n²)应当处于它们中间
O of n plus n squared, should logically be between them.
O(n²)相对于O(n)占优势地位
So this O of n squared thing kind of dominates this O of n thing,
所以你可以舍去那个次要因素
and so you drop that non dominant term.
n²是真正影响运行时间变化的因素
It’s the n squared that’s really going to drive how the runtime changes.
需要时你可以查阅一些更加学术化的解释
And if you want you can look up a more academic explanation
看看什么时候能舍去 什么时候不能
for when exactly you drop things and when exactly you can’t,
但这只是它的一个比较通俗的解释
but this is kinda layman’s explanation for it.
现在讲完了大O的基础知识 这是一个
We’ve now covered the very basic pieces of big O.
你必须掌握的 并且在面试时非常重要的概念
This is an incredibly important concept to master for your interviews
所以这里不要偷懒
so don’t be lazy here,
确保你真的能理解它
make sure you really really understand this
并通过大量练习来巩固你的理解
and try a whole bunch of exercises to solidify your understanding.
祝你好运
Good luck.

发表评论

译制信息
视频概述

今天讲的是作者最喜欢的话题之一 大O符号或算法效率,以及计算算法效率的四个规则。

听录译者

收集自网络

翻译译者

B11101001

审核员

审核团O

视频来源

https://www.youtube.com/watch?v=v4cd1O4zkGw

相关推荐