1901050017-自学训练营-MIT60001

[kagamiqyah]

学员信息

• 学号：1901050017
• 学习内容：MIT 6.0001
• 学习用时：130小时

学习笔记

介绍

MIT课程有12部分，另外有作业集pset0-5。 自学营提供lec1-12的视频和ppt，或者自行从网站下载。 另需一本《Introduction to computation and programming using Python》，建议看英文版，中文版也有，叫《Python编程导论》。

全部学完MIT课程以后，最大的感受是课程设计合理，完全为了让学生学进去而设计，视频里的教授们风趣幽默，语速适中，类比精确；ppt简洁易懂；书籍是视频+ppt的扩充，会讲解地更详细。而psets是考察对知识的掌握程度。

这里面最多出现的鼓励话语就是： Don't be intimidated.

课程旨在让我们学会用编程思维来解决问题，初步引导非相关专业的人们也可以写一些力所能及的小代码来为己所用。

记忆深刻的知识和工具

1. python是面向对象的语言，所以学习面向对象编程而使用的类class很重要。这个课程里花了的属性和使用
2. 写代码的重要方法：分而治之（divide and conquer）
3. 从找平方根的近似解学会了二分法和牛顿-拉佛森法（Bisection Search and Newton-Raphson Search)
4. 递归（recursion）在生活中的应用。
5. 函数（functions）的各种应用
6. 已升级为我的最爱python工具：网站pythontutor,它可以可视化python代码，尤其对于全局变量和局域变量、形参和实参、高阶函数（使用函数作为实参；map（）、lambda）的理解来说非常好用，一目了然。
7. 了解了有效算法是如何测定的，什么是概念复杂度，什么是计算复杂度，以便估算程序的计算复杂度，提高程序效率。

总结

• 我个人对编程思维的理解

  My personal understanding about computational thinking

It suits eveyone in all of world who eager to learn and use these applicable attitude and skill，not just the computer experts. 它适合全世界每个渴望学习和使用这些适用的看法和技能的人,不仅仅是那些计算机专家。

Computational thinking is a fundamental skill for everyone who be well-educated, not just for computer scientists.Well, the three R's( reading, writing, and arithmetic) are skills that every child need to master, in addtion, we should add computational thinking to the list of analytical ability. Afterall, it is a computer-age, child must adapt this tendency. 计算思维是每个有受教育基础的人需要具备的基本技能，而不仅仅是计算机科学家。阅读、写作和算术是孩子们需要掌握的技能，此外，我们还应该在分析能力名单中加入计算思维。毕竟这是计算机时代，孩子们需要适应这个潮流。

Computational thinking involves solving problems, designing systems, and understanding human behavior, by drawing on the concepts fundamental to computer science. Computational thinking includes a range of mental tools that reflect the breadth of the field of computer science. 计算思维包括利用计算机科学的基本概念解决问题、设计系统和理解人类行为。计算思维包括一系列反映计算机科学领域广度的思维工具。

Having to solve a particular problem, we might ask: How difficult is it to solve? and What’s the best way to solve it? 要解决一个特定的问题，我们可能会问:它有多难解决?最好的解决办法是什么?

Computer science provide such solid theoretical bases to answer such questions accurately and exactly. 计算机科学为准确回答这些问题提供了坚实的理论基础。

We just need to find a way to sunk into it，enjoy feeling of surfing the high-level knowlege sea. 我们只需要找到一种方式沉入进去，去享受在高级知识的海洋里冲浪的感觉。

[kagamiqyah]

学员信息

• 学号：1901050017

• 学习天数：day 1

• 学习内容：MIT course lecture 1 ppt+video

• 学习用时：60min

学习笔记

MIT course自学，需要先看课程ppt，再看课程video，课后运行一下课程codes，最后用psets来检验知识掌握程度。

1、 psets

Dr.bell说要提前看psets，这样看到术语时就不会一头雾水。因为之前已在psets里看到了，已经沉浸在脑子里里，她这时用的是sunk in，也就是沉浸的意思。下面是我找到的关于psets的定义和描述，那么提前看psets就属于李笑来老师说的过早引用。

网站原话：

What are Psets?

If you’re interested in MIT, you have to learn a little bit about psets.

Problem sets are the backbone of our teaching in many subjects; for many, problem-solving is the essence of the MIT education. Faculty vary as to the portion of course credit derived from psets. In some cases, the entire course is weighted towards exams so that psets are seen as a learning tool. In other courses, psets are a substantial portion of the final grade.

For the non-MIT folks out there:

a pset, or problem set, is MIT’s version of homework. And by “MIT’s version”, I mean that while a typical pset might only contain 5 problems, every one of those problems is incredibly difficult. And by “incredibly difficult”, I mean “incredibly difficult” – by MIT standards

现在清楚了，psets大概就是相当于一个主题作业集，但有一些难度，做作业的同时会检验知识是否掌握牢固。

2、不要害怕 don't be afraid.

学习新知识最容易被自己吓坏，而Dr.bell说最坏结果其实也就是重启计算机，在那之前要勇敢地敲代码，哪怕只是抄代码。

3、编程就是用计算机懂的语言来告诉它执行人类的指令，并且让其他人类也能读懂。

• 编程语言就是一种语言，和人类语言规则不同而已。
• 既然是语言，就会有规则。只要按照规则走，用计算机听得懂的语言写出，计算机就能执行你想让它执行的事情
  • 初始结构：
    1. 英语：words
    2. 编程语言：numbers,strings,simple operators,boleans
  • 语法：
    1. 英语：有效语法和无效语法
    2. 编程语言：有效语法和无效语法
  • 静态语义：
    1. 英语：语法有效但可能会静态语义不正确：I are a man
    2. 编程语言：静态语义不正确，语法就无效。
  • 语义：
    1. 英语：同一种表达会有不同意思
    2. 编程语言：一种表达只会有一种且只有一种意思，不会有歧义
  • 指出错误：
    1. 英语：如无必要，无人指出语法或语义错误
    2. 编程语言：可以立刻指出错误，并且告知错误类型
       • 语法错误：syntactic errors
       • 静态语义错误：static semantic errors
       • 计算机会执行与编程人期望不同的指令（因为编程人的错误）：different meaning than what programmer intended

4. python初步介绍

python，everything is an object.

它是操纵数据对象的一种编程语言。

• 对象从类型看，有各种类型，进而对各种类型有不同的操作。
• 对象从可测量看，分为可标量和不可标量。标量的：int，float，bool，NoneType

[kagamiqyah]

学员信息

学号：1901050017 学习天数：day2 学习内容：MIT Lecture2 +video 学习用时：1 hours

学员心得

summary

• string object type

• control flow

• indentation

• iteration and loops

1. string

数字 * string时，不是代表乘法，而是数字代表string重复的次数，比如：

print(5 * “eal“)

输出结果是：

ealealealealeal

2. control flow

if语句里的条件都有boolean值，True or False，如果值是True，那就执行模块

3. indentation

缩进很重要，是模块间区分的重要形式。

4. iteration and loops

for语句和while语句都能写出循环程序，但他们各有不同。老师讲的很好，对循环语句又加深了一遍印象。

还是要多做练习，自己敲代码。

[kagamiqyah]

学员信息

学号：1901050017 学习天数：day3 学习内容：MIT Lecture3 学习用时： 2 hours

学习心得

summary

• string manipulation
• guess and check algorithms
• approximate solutions
• bisection method

知识要点

string特性

string[]的这个形式可以来检索string里的任何位置的字符，可以单一检索，还可以切片检索。 len()这个函数可以用来计算string的长度，在loops里应用很多。 string的特性是不能更改里面的任何字符，但可以以下面例子的方式来更改。

s = "hello"
s = 'y'+s[1:len(s)]

iteration时，用for 比 while 更简便

下面语块意思一样

for char in word:

i = 0
while i < len(word):
    char = word[i]
    ...
    i += 1

guess-and-check

利用求立方根cube root的三种方法来说明guess-and-check 1.给定数字的for loops方法 例： 正数：

cube = 8120601
for guess in range(cube+1):
    if guess**3 == cube:
        print("Cube root of", cube, "is", guess)

结果：

Cube root of 8120601 is 201

负数：

cube = -8120601
for guess in range(abs(cube)+1):
    if guess**3 >= abs(cube):
        break
if guess**3 != abs(cube):
    print(cube, 'is not a perfect cube')
else:
    if cube < 0:
        guess = -guess
    print('Cube root of '+str(cube)+' is '+str(guess))

结果：

Cube root of -8120601 is -201

2. APPROXIMATE SOLUTIONS

   cube = 27
   epsilon = 0.01
   guess = 0.0
   increment = 0.0001
   num_guesses = 0
   while abs(guess**3 - cube) >= epsilon and guess <= cube :
   guess += increment
   num_guesses += 1
   print('num_guesses =', num_guesses)
   if abs(guess**3 - cube) >= epsilon:
   print('Failed on cube root of', cube)
   else:
   print(guess, 'is close to the cube root of', cube)

   结果：

   num_guesses = 29997 2.999700000001906 is close to the cube root of 27

3.BISECTION SEARCH 适合用户输入时使用这种方法 下面这个语块只适用于正数

cube = 27
#cube = 8120601
# won't work with x < 1 because initial upper bound is less than ans
#cube = 0.25
epsilon = 0.01
num_guesses = 0
low = 0
high = cube
guess = (high + low)/2.0
while abs(guess**3 - cube) >= epsilon:
   if guess**3 < cube:
       # look only in upper half search space
       low = guess
   else:
       # look only in lower half search space
       high = guess
   # next guess is halfway in search space
   guess = (high + low)/2.0
   num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to the cube root of', cube)

结果：

num_guesses = 14 3.000091552734375 is close to the cube root of 27

总结

• 解决一个问题有很多方法，知识掌握地越多，越扎实，方法也就越多。
• 方法多是为了应对各种情况，在面临选择时做出最好的决定
• 这节课让我明白了解字符串的特性，并且学会检索和调用，在编程中是很有用的。
• 学会了完全枚举法 exhaustive enumeration。遇到问题，先给个值，再看看对不对，不对的话接着找，直到找到最接近的。
• 在遍历时，用for比while语句更方便。
• 学到lec3时，我更加确定了提前看ppt的好处，因为先看了英文，之后看视频的时候可以练到听力。提前敲代码，也更有助于在看视频时跟上老师的速度。

[kagamiqyah]

学员信息

学号：1901050017 学习天数：day 4 学习内容：MIT Lecture4 学习用时： 2 hours

学习心得

1. 自定义函数的组成部分有keyword，name，parameters，docstrings，body。
2. 函数内的return和print的区别：
   • return只在函数内有效；print在函数外也能用
   • return在函数里只执行一次；print可执行很多次。
   • return后面的code不会被执行；print后面的code还可以执行。
   • return把值给予函数caller；print把值显现在console上。

3. 教授说python tutor是解决函数scope最好的朋友。我试了，觉得果真如教授所说，太好用了，对于理解函数里的全局变量，局部变量，形式函数，实际函数都有很深的理解.我目前不知道如何上传截图，无法图示出它的好。www.pythontutor.com 通过使用这个网站我现在通过纸和笔也能一步一步手动debug自定义函数了，至少简单的没问题，

   这就是我这节课最大的收获

[kagamiqyah]

学员信息

学号：1901050017 学习天数：day 5 学习内容：MIT lec5 学习用时： 3小时（ppt+视频+课后练习+python tutor检验）

学习心得

关键词

• list
• tuple
• alias
• clone
• mutable
• side effect

对于课程的理解，还是在于实际操作。 alias通过老师的类比，完全明白了，就是相当于给一个object起了一个别名，所以它的属性要变一起变。 clone是克隆了一个object，不会引起side effect。 为了巩固知识，我把练习中的代码都敲了一遍，并在python tutor里走了一遍。在敲代码的过程中，能看见肉眼看不见的线索，再一次理解代码的意义；在python tutor的一步一步图释中，具象化了tuple、list、string的各种变化。 下面是lec5文件里的最后一道题，我都把结果都在每一行代码里注释里一遍。

cool = ['blue', 'green']
warm = ['red', 'yellow', 'orange']
print(cool)
print(warm)

colors1 = [cool]  #[['blue', 'green']]
print(colors1)    
colors1.append(warm)  #colors1 =  [['blue', 'green'], ['red', 'yellow', 'orange']]
print('colors1 = ', colors1)

colors2 = [['blue', 'green'],
          ['red', 'yellow', 'orange']]
print('colors2 =', colors2)   #colors2 = [['blue', 'green'],['red', 'yellow', 'orange']]

warm.remove('red')   #['blue', 'green']
print('colors1 = ', colors1)   # colors1 =  [['blue', 'green'], ['yellow', 'orange']]
print('colors2 =', colors2)    # colors2 = [['blue', 'green'], ['red', 'yellow', 'orange']]

for e in colors1:
    print('e =', e)       #e = ['blue', 'green'] e = ['yellow', 'orange']

for e in colors1:
    if type(e) == list:
        for e1 in e:
            print(e1)           #blue green yellow orange
    else:
        print(e)

flat = cool + warm
print('flat =', flat)   #flat = ['blue', 'green', 'yellow', 'orange']

print(flat.sort())         #None
print('flat =', flat)       #flat = ['blue', 'green', 'orange', 'yellow']

new_flat = sorted(flat, reverse = True)
print('flat =', flat)          #flat = ['blue', 'green', 'orange', 'yellow']
print('new_flat =', new_flat)    #new_flat = ['yellow', 'orange', 'green', 'blue']

cool[1] = 'black'
print(cool)        #['blue', 'black']
print(colors1)     #[['blue', 'black'], ['yellow', 'orange']]

pythontutor显示结果，非常清晰

最终打印结果

[kagamiqyah]

学员信息

学号：1901050017 学习天数：day 6 学习内容：MIT lec6 学习用时： 2小时 ppt+视频

学习心得

1. 到递归了。又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也可以理解为自我复制的过程。 例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。
2. 目前看到ppt里面的factorial 阶乘，关于示例函数，我按照惯例，为了完全明白，使用了python tutor的工具都迭代了一遍。再加上看维基百科和python tutorial，算是加强了印象。 阶乘还算好理解，但是汉诺塔的代码对我来说有点困难了，在tutor里跑了一遍，又加上print走了一遍，才勉强理解

   
   def printMove(fr, to):
   print('move from ' + str(fr) + ' to ' + str(to))

def Towers(n, fr, to, spare): if n == 1: printMove(fr, to) else: Towers(n-1, fr, spare, to) Towers(1, fr, to, spare) Towers(n-1, spare, to, fr)

print(Towers(4, 'P1', 'P2', 'P3'))

结果如下：

>move from P1 to P3
move from P1 to P2
move from P3 to P2
move from P1 to P3
move from P2 to P1
move from P2 to P3
move from P1 to P3
move from P1 to P2
move from P3 to P2
move from P3 to P1
move from P2 to P1
move from P3 to P2
move from P1 to P3
move from P1 to P2
move from P3 to P2
None

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 7 学习内容：MIT lec7 学习用时： 2小时 ppt+视频

学习心得：

• 学到了assertion这个用法，和try，except功能类似。但不如except全面。它不会回应之前没有预期的情况。

• assertion可以作为except的补充，而且它能很好地指出bad data input。

• raise是抛出一个错误，自定义错误的说明

• 无论看多少遍，为了彻底理解try，except, finally, assert,raise,还是动手敲代码吧，这是我理解最快的途径。

try，except，finally:

def divideNew(x, y):
    try:
        result = x / y
    except ZeroDivisionError:
        print ("division by zero! " )
    except TypeError:
        divideNew(int(x), int(y))
    except:
        raise ValueError('something get wrong.')
    else:
        print ("result is", result)
    finally:
        print ("executing finally clause")

divideNew(3,4)
divideNew(3,0)

assert:

def divideNew(x, y):
    assert y !=0 ,'division by zero!'
    print ("executing finally clause")
    return x / y
divideNew(3,4)
divideNew(3,0)

[kagamiqyah]

学员信息： 学号：1901050017 学习天数：day 8 学习内容：MIT lec8 学习用时： 2小时 ppt+视频

学习心得：

• python，面向对象的语言，它的特征是封装、继承、多态

• 简介了类class，就是实物的虚拟数据，比如，人类就是一种类，还有鸟类、植物类，用程序语言的方式来表达出来，并分成一类一类的。

• 多态：对不同的类的对象使用同样的操作。 封装：对外部世界隐藏对象的工作细节。 继承：以普通的类为基础类建立专门的类对象。 面向对象的三个基本特征：封装，继承，多态。

• 面向的对象的属性： 静态属性： 私有属性 实例属性 类属性(类变量) 动态属性(就是方法)：实例方法 私有方法--和私有属性一样是双下划线开始的，调用形式和私有属性一样，只能通过类中的方法调用

用代码来示范一下class

class People(object):
    def __init__(self,country, name,age=36):  #构造方法
        self.country = country  #实例属性
        self.name = name
        self.__age = age        #私有属性

    def __del__(self):  #析构函数
        print(f'{self.name.capitalize()}has died.')

    def get_info(self):  #实例方法
        print(f'The{self.name}info',center(50,"-"))
        print(f'The{self.name}comes from{self.country} , is{self.__age}old' )

a = People("China","hitler",20) #实例化一个类时，这时候构造函数会自动执行

a.get_info() #通过实例访问类中的实例方法 结果： -------------------The hitler info-------------------- The hitler comes from China, is 20 old

在类中定义属性时，分为私有属性和公有属性。双下划线开始的是私有属性，例如self.__age属性， 而像self.country和self.name属性则是公有属性.无论是那种属性，都是通过实例化来实现的

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 9 学习内容：MIT lec8 学习用时： 3小时 ppt+视频+课后习题

学习心得：

加深印象，深刻理解

• 看了视频两遍 + 练习题，知道了self就是代表class的实例，并且在def时self这个参数不能省略

• 每一个具体的对象可以从类中继承相同的方法，只是各自的数据不同。

• 用init来绑定类的属性，里面的第一参数永远是self，这样其他属性就自动绑定这个实例self了。

• 接下来就是封装了，也就是把内部定义访问数据的函数。这样调用起来就很容易，只用就可以了，不用知道实现的细节。

写代码永远是掌握知识最好的途径。 在这章的code里，第二部分的代码建议尝试一下写分数的乘法和除法函数，并尝试写一下分数的最大公约数的函数。 我尝试了一下，应该不是最简洁的，用lambda函数来排序更适合参数很多的情况下 __mult__,__div__,__GCD__ 是我加到里面去的自定义函数，用来表示分数的乘法，除法，和最大公约数

class Fraction(object):
    """
    A number represented as a fraction
    """
    def __init__(self, num, denom):
        """ num and denom are integers """
        assert type(num) == int and type(denom) == int, "ints not used"
        self.num = num
        self.denom = denom
    def __str__(self):
        """ Retunrs a string representation of self """
        return str(self.num) + "/" + str(self.denom)
    def __add__(self, other):
        """ Returns a new fraction representing the addition """
        top = self.num*other.denom + self.denom*other.num
        bott = self.denom*other.denom
        return Fraction(top, bott)
    def __sub__(self, other):
        """ Returns a new fraction representing the subtraction """
        top = self.num*other.denom - self.denom*other.num
        bott = self.denom*other.denom
        return Fraction(top, bott)
    def __mult__(self,other):
        """ Returns a new fraction representing the multiplition"""
        top = self.num * other.num
        bott = self.denom * other.denom
        return Fraction(top, bott)
    def __div__(self,other):
        """ Returns a new fraction representing the division"""
        top = self.num * other.denom
        bott = self.denom * other.num
        return Fraction(top,bott)
    def __GCD__(self):
        """ Returns a number representing the gcd of the two fraction"""
        x = self.num
        y = self.denom
        l = [x,y]
        l.sort()
        for i in range(1,l[1] + 1):
            if l[0] % i ==0 and l[1] % i == 0:
                gcd = i
        return gcd
    def __float__(self):
        """ Returns a float value of the fraction """
        return self.num/self.denom
    def inverse(self):
        """ Returns a new fraction representing 1/self """
        return Fraction(self.denom, self.num)

a = Fraction(1,4) b = Fraction(3,4) c = a + b # c is a Fraction object print(c) print(float(c)) print(Fraction.add(a,b)) print(Fraction.sub(a,b)) print(Fraction.float(c)) print(float(b.inverse())) print(Fraction.GCD(b))

结果：

16/16 1.0 16/16 -8/16 1.0 1.3333333333333333 1

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 10 学习内容：MIT lec9 ppt twice 学习用时： 1小时

学习心得：

summary:

• class inheritance
• getter and setter
• information hiding
• class variables

class有parent class（superclass）和 child class（subclass）

class Animal（object）vs class Cat（Animal） #前者为parent class ，后者为child class，后者可以直接继承前者的所有属性，并定义一些属于自己的新函数，并且可以override覆盖__str__method.在python里面，一个子child class 可以继承多个parent class，即使由多个parent class可能有重名但不同用法的function，在python里，如果遇到重名的function，默认call的是先继承的parent class下的function。

get_和set_这两种是为了由外部访问class数据属性时的自定义函数，在外部访问时，用get这个method来调用数据，可以有效避免bug

#create the class Ghost
class Ghost():
    life = 3

    def attack(self):
        print('Ouch!')
        self.life -= 1

    def checkLife(self):
        print(self.life, 'life left')

#create objects, objects are separate individuals, each is like a copy of the class
Ghost1 = Ghost()
Ghost2 = Ghost()

Ghost2.attack()
Ghost2.attack()
Ghost2.checkLife()

Ghost1.checkLife()

结果：

Ouch! Ouch! 1 life left 3 life left

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 11 学习内容：MIT lec9 video 学习用时： 2小时

学习心得：

在我心里，class和正则表达式都很重要，都很难掌握，所以我在lec8和lec9时都格外地用心学习。遇到不会或难懂的知识点时，我就打开python tutor去敲一遍，看看一步一步的语句是如何进行数据分配的，自定义函数都分别是什么功能。在这里我要着重赞美python tutor，它是抽象转化为具象的最好工具。

覆盖和继承 override & inheritance

• 覆盖 override 是指当执行语句时，系统会先在子类里寻找同名函数，如果找到的话，那就直接执行（书里用的词是invoke），就不会去大一级的类里去找了。

• 继承 inheritance 是指子类天然从大一级的类里继承所有功能，但也可以在自己的类里添加新功能。我的理解就是就像孩子从家长那里继承基因，但同时会有于父辈不一样的新技能。

模仿真实世界

面向对象编程OOP 理解起来的话就是和真实世界接轨，模仿真实世界。就像我们开车，玩视频游戏一样，我们不需要直到它的内部构造，只要掌握使用方法，就可以开始了；如何分类各种车和游戏机呢，就是按照他们的特征来进行分类。我们人类的大脑天然具有为事物分类的特征，而在电脑里实现这一过程，就需要一步一步告诉电脑该如何分类，就如李骏老师所说，电脑就是个婴儿，它需要我们程序员来告诉，如何用它能听懂的语言来指导每一步，最终实现我们的目的。

好记性不如烂笔头

看得再明白也不如自己敲一敲记得深。

def getClass(self): 
    return self.year
def getClass():
    return self.year

这两个自定义函数，在视频练习里，在选择答案时我就选择了第二个，原因是因为还是记得不牢靠。而在定义getter时，self一定要写在括号里，当形式参数。

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 12 学习内容：MIT lec10 ppt + video 学习用时： 2小时

学习心得：

summary:

• measuring orders of growth of algorithms

• big "oh" notation

• complexity classes

会写程序是第一步，之后还要写出运行最快，执行最有效率，最优化的程序。 那么如何写出优化、最有效率的程序，这是有方法来评估的，这也是这章所讲的。 timing program这个方法不适合需用户输入参数时 counting operations 没有明确定义哪些operations不用去数，从而也无法评估用这个方法的程序最有效 所以还是需要一种更好的方式来评估哪种最有效。这是我明天的任务。

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 13 学习内容：MIT lec10 ppt + video 学习用时： 2小时

学习心得：

summary: Why did we need to think about whether the program is correct and efficiency? because it should produce results that can be relied upon: warning system of airplane crush, complete transactions through evaluating the utility of database systems. so we do desire the efficient programs so bad. but...... that's not easy.

we should build the programs that are conceptual complexity as an effort to reduce its computational complexity. of course, it is a dilemma and difficult to write.

• linear search: the best-case running time is independent of the size of L.

• log-linear search: each of which depends upon the size of the inputs.

• polynomial search: their complexity grows as the square of the size of their input.

• exponential search: also depend on the size of the input.

linear:O(1) denotes constant running time. 
log:O(log n) denotes logarithmic running time. 
linear:O(n) denotes linear running time. 
log:O(n log n) denotes log-linear running time. 
polynomial: O(n^k) denotes polynomial running time. Notice that k is a constant. 
exponential:O(c^n) denotes exponential running time. 

Does this mean that we cannot use computation to tackle exponentially hard problems? Absolutely not. It means that we have to find algorithms that provide approximate solutions to these problems or that find perfect solutions on some instances of the problem.

we will see more in later chapters

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 14 学习内容：MIT lec11 ppt + video 学习用时： 2小时

学习心得：

再一次见到了bisection search，这次是用它来讲每一步的程序复杂性的。二分法的程序的每一步都属于哪种O notation 复杂类，再一次感叹程序员思维的魅力。

而在这lec10 和 lec 11的学习中，我用了mit 教材书作为辅助，才能把学习进行下去，感谢严雨同学的分享。知识的学习除了实践还有真的需要读官方讲义或原版教材，因为知识的扎实掌握离不开重复性和不同角度的讲解。

时间复杂度是一个函数，它定量描述了该算法的运行时间:o(1), o(n), o(logn), o(nlogn)

O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

用通俗的话来描述，我们假设n=1所需的时间为1秒。那么当n = 10，000时。

比如：

O（1）的算法需要1秒执行完毕。

O（n）的算法需要10，000秒 ≈ 2.7小时 执行完毕。

O（n2）的算法需要100，000，000秒 ≈ 3.17年 执行完毕。

O（n！）的算法需要XXXXXXXX(系统的计算器已经算不出来了)。

可见算法的时间复杂度影响有多大。

所以O（1）和O（n）差了2.7小时，区别显而易见。

O(1)复杂度是与输入数据无关，O(n)是与输入数据成正比。

再比如: O (logn)，将一个数据集分成两半,然后将分开的每一半再分成两半,依此类推。当数据增大n倍时，耗时增大logn倍（比如，这里的log是以2为底的，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。

例：二分法search就是O (logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

O (nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。 例：归并排序就是O (nlogn)的时间复杂度。

归并排序是指归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

example：

设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为14；

代码：

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result
print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])

p.s.

O (1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。

例：哈希算法就是典型的O (1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）

[kagamiqyah]

学员信息：

学号：1901050017 学习天数：day 15 学习内容：MIT lec12 ppt + video 学习用时： 2小时

学习心得：

• bisection search implementation # the search makes me so obsessive.

def bisect_search2(L,e):
    def bisect_search_helper(L,e,low,high):
        if high == low:
            return L[low] == e
        mid = (low + high)// 2
        if L[mid] == e:
            return True
        elif L[mid] > e:
            if low == mid: #nothing left to search
                return False
            else:
                return bisect_search_helper(L,e,low,mid - 1)
        else:
            return bisect_search_helper(L,e,mid + 1,high)
    if len(L) ==0:
        return False
    else:
        return bisect_search_helper(L,e,0,len(L) - 1)

L=[3,6,68,76,4,2,56,74,63,52,36,70,8,1,51]   
print(bisect_search2(L,6))

• My personal understanding of computational thinking

It suits everyone in all of the worlds who eager to learn and use these applicable attitudes and skill，not just the computer experts. 它适合全世界每个渴望学习和使用这些适用的看法和技能的人,不仅仅是那些计算机专家。

Computational thinking is a fundamental skill for everyone who is well-educated, not just for computer scientists. Well, the three R's( reading, writing, and arithmetic) are skills that every child need to master, in addition, we should add computational thinking to the list of analytical ability. After all, it is a computer-age, the child must adapt to this tendency. 计算思维是每个有受教育基础的人需要具备的基本技能，而不仅仅是计算机科学家。阅读、写作和算术是孩子们需要掌握的技能，此外，我们还应该在分析能力名单中加入计算思维。毕竟这是计算机时代，孩子们需要适应这个潮流。

Computational thinking involves solving problems, designing systems, and understanding human behavior, by drawing on the concepts fundamental to computer science. Computational thinking includes a range of mental tools that reflect the breadth of the field of computer science. 计算思维包括利用计算机科学的基本概念解决问题、设计系统和理解人类行为。计算思维包括一系列反映计算机科学领域广度的思维工具。

Having to solve a particular problem, we might ask: How difficult is it to solve? and What’s the best way to solve it? 要解决一个特定的问题，我们可能会问:它有多难解决? 最好的解决办法是什么?

Computer science provides such solid theoretical bases to answer such questions accurately and exactly. 计算机科学为准确回答这些问题提供了坚实的理论基础。

We just need to find a way to sink into it，enjoy feeling of surfing the high-level knowledge sea. 我们只需要找到一种方式沉入进去，去享受在高级知识的海洋里冲浪的感觉。