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
最好情形是在哪种输入下执行最快、计算量最少,这没太大意义。
平均情形很难计算,因为要知道输入的概率是否均匀,还取决于用户输入。
我们最关心的是最坏情形,它是效率的上界。另外,很多情况下发生的就是最坏情形。
在查找时,经常会发生最坏情形。因此我们一般用最坏情形分析。
分享到:
相关推荐
“MIT计算机科学及编程导论”网上公开课的讲义 http://v.163.com/special/opencourse/bianchengdaolun.html
公开课资源,MIT 计算机科学导论及Python编程 ppt 课件MIT 计算机科学导论及Python编程 ppt 课件MIT 计算机科学导论及Python编程 ppt 课件MIT 计算机科学导论及Python编程 ppt 课件MIT 计算机科学导论及Python编程 ...
[计算机科学及编程导论][MIT][相关代码(Python)]cs600-2008 # 翻译制作:ocourse.org # 课程讨论版:http://ocourse.org/bbs/forum.php?mod=forumdisplay&fid=29 # by yoeo24
资源名称:[MIT课程]计算机科学及编程导论视频教程[中英字幕]资源目录:【】06039b1c783a8fa3f60f611ffc2dda11【】0c793b5dd05b7f677279ce26997d77b3【】11c609aef12a8492f89ac9619ff5b999【】1769b5bca73d0258201c9...
麻省理工学院公开课:计算机科学与编程导论的课件与习题(英文版)
mit经典入门课程“计算机科学与编程导论”。 视频中的代码不清晰,找到了课程提供的代码。
MIT的这门课程适用于那些拥有很少或没有编程经验的学生,它致力于使学生理解计算机在解决问题中的作用,并且帮助学生,不论其专业,使他们对于能够完成有用的小程序的目标充满信心
麻省理工开放课程:计算机科学及编程导论1-7练习代码
算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT算法导论MIT
麻省理工学院公开课:计算机科学及编程导论 本课程共24集 翻译完 欢迎学习 讲师:Prof. Eric Grimson Prof. John Guttag - 麻省理工学院计算机科学与工程系的教授 - 里贾纳大数学和学物理学士、麻省理工学院数学博士...
本文档为MIT《编程导论》(课程代码6.0001)的课后习题集第二次作业,主要是对函数、循环的应用,难度不大,因为有一步步的引导,但也不太简单,就好像是要跳起来才能摘到的苹果。
MIT算法导论 MIT算法导论 MIT算法导论 MIT算法导论 MIT算法导论
MIT计算机导论中的高频词汇,方便学习原文。配合视频更棒
MIT 算法导论part3MIT 算法导论part3MIT 算法导论part3MIT 算法导论part3MIT 算法导论part3MIT 算法导论part3
美国著名大学MIT的算法导论公开课教材,有排序、树、Hash等经典算法的讲解
《算法导论》从一定深度上涵盖了算法的诸多方面,同时其讲授和分析方法又兼顾了各个层次读者的接受能力。这里提供的是该教程第二版的课件,为麻省理工大学制作,英文版,pdf格式,用Abobe Reader全屏查看可以和ppt...
MIT 计算机科学专业 离散数学
这是关于MIT计算机本科生课程6.00的详细文档!
MIT经典教材之算法导论 Introduction.to.algorithms 完整版+教材+讲义+习题答案