MIT《计算机科学与编程导论》第七讲

Section 1

mutable

L1 = [1, 2, 3]

L2 = L1

L1[0] = 4

print L2 -> [4, 2, 3]

immutable

a = 1

b = a

a = 2

print b - 1

Dictionaries 字典类型

-mutable

-not ordered

-generalized indexing

Section 2

Pseudocode 伪代码

1.Module

2.Data type

3.Flow of control

4.Abstraction

Efficency 效率

一只手打开电脑桌上一盏小台灯，同时另一只手点击一台2Ghz电脑的运行键。

在光照到桌面时，电脑可以运行两条指令！This is amazing！

从这里毕业的一名学生现在是谷歌搜索算法的核心开发人员。他非常聪明，设计了

非常好的算法。但是对于一般人来说，并不容易也不需要设计新算法。

In general, it's hard to come up with the really clever algorithm.

What you're much better at doing is saying how do I take the problem I've got

and map it into a class of algorithm about which I know and use the efficiencies

of those to try and figure out how to make it work.

Another way of say it is, efficiency is really about choice of algorithm. And we want

to help you learn how to map a problem into a class of algorithm of some efficiency.

一般说来，想到好算法并不容易。你们要做的一般是，如何把准备处理问题适用到

一些已知的算法中。然后找出效率最高的来搞定它！效率其实就是关于算法选择的。

我们要教会你的是如何将问题用高效的算法来解决。

How do we think about effciency? Typically, there's two things we want to measure:

space & time.

When we talk about space, what we usually refer to is, how muchcomputer memory

does it take to complete a computation of a particular size?And by that, I mean,

not how much memory do I need to store the size of the input.It's really how much

internal memory do I use up as I go through the computation?

In this course, we really focus on the time. What is the number of the basic steps

needed as a function of the input size?

我们该如何考虑效率？一般要评估两样：空间和时间。谈到空间，我们指的是需要多少

计算机内存来完成一定量的计算。这并不是说，需要多大内存来存放输入，说的是运算时

要用掉多少内存。

这门课上不需要太关注空间，而是主要关注时间。计算基本步骤数作为输入规模的函数

是怎样的。

（不应该运行程序看多久运行完。因为这钟运行时间会受到很多因素影响，如机器的配置，

用什么语言实现，Python的版本等等。）

We're going to assume a particular model, called a random access model.

Which basically says, we're going to assume that the length of time it takes me to

get to any location in memory is constant. And the second assumption we're going

to make is the basic primitive steps take constant time, same amount of time to compute.

假设一个模型，称作随机存取模型。大体上说是，我们假设到内存某个地址时间长度是

一个常数。我们要作的第二条假设是基本指令不但耗常数时间，而且执行时间相同。

（对于每种编程语言不全是这样，但这个模型不错。）

Random Access Model and 3 cases to analyze

- Best case

- Worst case

- Average case

最好情形是在哪种输入下执行最快、计算量最少，这没太大意义。

平均情形很难计算，因为要知道输入的概率是否均匀，还取决于用户输入。

我们最关心的是最坏情形，它是效率的上界。另外，很多情况下发生的就是最坏情形。

在查找时，经常会发生最坏情形。因此我们一般用最坏情形分析。