1901020029-自学训练营-MIT60001-Day21~30

发表于 分类于 评论数：

学员信息

  • 学号：1901020029
  • 学习内容：MIT6.0001课程打卡21-30天
  • 学习用时：18小时

学习笔记

第21天：20190717

学习时间：1.5小时
学习内容：MIT Lecture 10 + PPT（21-39）
学习收获：
1、程序复杂度级别的组合：

  • 分析函数内部语句
  • 应用某些规则，聚焦于主项
  • O():的乘法法则用于嵌套语句/循环
  • O(f(n)) * O(g(n)) is O(f(n) * g(n))

2、复杂度级别，下述复杂度级别按顺序由低到高

  • O(1)表示常数运行时间
  • O(logn)表示对数运行时间
  • O(n)表示线性运行时间
  • O(n logn)表示对数线性运行时间
  • O(n^c)表示多项式运行时间（c是一个常数）
  • O(c^n)表示指数运行时间

3、简单的迭代循环算法是典型的线性复杂度。
4、对无序列表和有序列表进行线性搜索，其总体复杂度都是O(n)，这里的n是列表长度len(L)。
注意：尽管两种搜索方法的运行时间可能有差别，但增长的量级是相同的。
5、用子集测试的函数例子来说明嵌套循环的复杂度是平方复杂度O(n^2)。

第22天：20190718

学习时间：1小时
学习内容：MIT Lecture 11前10min + PPT（1-10）
学习收获：
1、继续理解程序的效率，从设计开发程序的角度理解当输入规模变大时，所耗成本-时间的增长程度，考虑选择合适的算法以达成目标，继续讨论算法复杂度。
2、为什么要懂得程序的效率？

  • 我们怎样评估当需要解决特定规模的问题时，需要花费多少时间成本。
  • 我们怎样关联算法的时间效率，来选择算法的设计。对我们要解决的特定问题有基础的时间限制吗？

3、以下复杂性类是复杂度从上到下依次递增的，因此我们实现算法设计时，希望在序列的顶端，如果程序复杂度随输入规模的增长呈指数递增，程序的实现将是灾难性的。

  • O(1)
  • O(logn)
  • O(n)
  • O(n logn)
  • O(n^c)
  • O(c^n)

4、常数复杂度

  • 复杂度与输入规模无关
  • 这类程序很少有有趣的算法，但有一些代码片段可以归于此类
  • 可以有循环或递归调用，但迭代或调用次数与输入规模无关

5、对数复杂度

  • 复杂度的增长是一个输入的对数
  • 例子：二分搜索、列表的二分查找
第23天：20190720

学习时间：1.5小时
学习内容：MIT Lecture 11(10-20min )+ PPT（10-14）
学习收获：
1、继续学习具有对数复杂度的二分搜索例子。
2、关于二分搜索：

  • 假定我们想知道是否一个特定元素存在于一个列表中
  • 看上次我们可以仅仅沿着列表走，检查每一个元素
  • 复杂度与列表长度呈线性关系
  • 假定我们知道列表是从最小到最大有序排列
    • 看那个有序搜索在复杂度上仍然是线性的
    • 我们能做的更好吗？
      1. 选一个索引，i，将列表一分为二
      2. 问是否L[i]==e
      3. 如果不等于，问是否L[i]是比e更大多更小
      4. 依据答案，搜索对e而言的左侧或右侧的另一半L

一个新版的分而治之算法出现

  • 问题被分解成更小的版本(更小的列表)，加某些简单操作
  • 对更小版本的答案是对原始问题的答案

二分搜索复杂度分析

  • 当对半减小列表到只剩一个元素时结束搜索，1=n/2i，所以i=logn
  • 递归的复杂度是O(log n)——这里n是len(L)

3、二分搜索代码的实现1：

1
2
3
4
5
6
7
8
9
10
11
def bisect_search1(L, e):
    if L == []:
        return False
    elif len(L) == 1:
        return L[0] == e
    else:
        half = len(L)//2
        if L[half] > e:
            return bisect_search1(L[:half], e)
        else:
            return bisect_search1(L[half:], e)

4、二分搜索方法1的复杂度：implementation1-bisect_search1

  • O(log n)分半搜索调用
    • 每一次递归调用，被搜索的范围规模被减半
    • 如果原始规模是n，最差的情况直到搜索范围为1是当n/(2^k)=1，或当k=logn
  • O(n)对每一次分半搜索调用拷贝列表
    • 这是建立每一次调用的成本，所以对每一层递归这样做
  • O(log n)*O(n)得出O(n logn)
  • 如果我们足够仔细，注意到被拷贝的列表长度在每一次递归调用时也被减半了
    • 结果是拷贝的总成本是O(n)并且统治了递归调用产生的logn成本
第24天：20190721

学习时间：40分钟
学习内容：MIT Lecture 11 PPT（15-19）
学习收获：
1、二分搜索的替代方案

  • 每一步仍然通过两个因素缩减问题的规模
  • 但是仅记录被搜索的列表的低和高部分
  • 避免拷贝列表
  • 递归的复杂度又是O(logn)——这里n是len(L)

2、分半搜索代码的实现2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)

3、二分搜索方法2的复杂度：implementation2-bisect_search2

  • O(log n)分半搜索调用
    • 每一次递归调用，被搜索的范围规模被减半
    • 如果原始规模是n，最差的情况直到搜索范围为1是当n/(2^k)=1，或当k=logn
  • 通过列表和目录作为参数
  • 列表从不拷贝，只是作为指示器被重新通过
  • 因此O(1)工作于每一个递归调用
  • O(logn)*O(1)得出O(logn)

4、对数复杂度的数字转换为字符串的例子：

1
2
3
4
5
6
7
8
9
def intToStr(i):
    digits = '0123456789'
    if i == 0:
        return '0'
    result = ''
    while i > 0:
        result = digits[i%10]+result
        i = i//10
    return result
  • 因为没有函数调用所以仅需检查循环语句
  • 在while循环中，迭代步数是常数
  • 循环多少次？
    • 多少次一个数可以用i除以10做整数除法
    • O(log(i))
第25天：20190723

学习时间：3小时
学习内容：MIT Lecture 11 PPT（20-39）
学习收获：
1、在学习过程中还是会偷懒，比如视频课听的云里雾里时，就会先把视频放在一边，去理解PPT，尝试自己翻译理解PPT，今天回头再听视频课，发现理解的多一些了，同时也校验了自己翻译时的很多错误理解。又遇到了一节课，要打卡很多天才能完成。
2、这节课老师在用各种案例教我们理解算法的效率，懂得程序的复杂度概念，知道程序运行时伴随输入规模的增长，程序的计算复杂度会以怎样的方式递增，会用大O法进行评估。
3、线性复杂度的算法实例：迭代和递归
3.1、迭代算法的O()

  • 复杂性可以依赖迭代调用的次数

    1
    2
    3
    4
    5
    def fact_iter(n):
        prod = 1
        for i in range(1, n+1):
            prod *= i
        return prod

  • 总体复杂度为O(n)——n次循环，每次花费常数成本

3.2、递归算法的O()

1
2
3
4
5
6
def fact_recur(n):
    """assume n>=0"""
    if n <=1:
        return 1
    else:
        return n*fact_recur(n-1)
  • 估算递归因子
  • 如果你计时，会发现它运行的比迭代版本慢一些，因为函数调用的原因
  • 复杂度仍然是O(n)，因为函数调用的次数和n呈线性关系
  • 迭代和递归因子的实现具有相同的增长订单

4、对数线性复杂度：非常强大的算法，普遍的应用在合并排序中，下节课将详细介绍
5、多项式复杂度：最常见的是二项式复杂度，即复杂度按照输入规模的平方增长；通常在有嵌套循环或嵌套递归的地方出现
6、指数复杂度

  • 递归函数里有超过一个递归调用时
    • 汉诺塔
  • 许多重要问题本身就是指数性质的
    • 很不幸，成本很高
    • 将引导我们考虑近似解，这样可以更快地获得合理的答案

6.1、汉诺塔的复杂度：这里老师用数学公式推导出解决汉诺塔问题的时间成本，即增长订单为指数级的增长O(2^n)
6.2、功率集的概念，解决给定一个没有重复的整数集，然后生成该集合的全部子集的方案。用递归思维来思考：

  • 我们想生成从1到n的整数功率集
  • 界定我们能生成从1到n-1的整数功率集
  • 那么所有那些子集属于更大的功率集（选择不包括n）；并且当n加到所有那些子集后也属于更大的功率集（选择包括n）
  • 非常好的递归描述
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def genSubsets(L):
        res = []
        if len(L)==0:
            return [[]]
        smaller = genSubsets(L[:-1])
        extra = L[-1:]
        new = []
        for small in smaller:
            new.append(small+extra)
        return smaller+new

对此递归函数的复杂度理解，函数的计算时间包括解决更小问题的时间，加上在更小的问题里拷贝全部元素所需的时间，最终计算出功率集的复杂度为O(2^n)

7、复杂度等级

  • O(1)—代码不依赖于问题的规模
  • O(log n)—通过进程每次将问题缩减为一半
  • O(n)—简单的迭代或递归程序
  • O(n log n)—下节课会看到
  • O(n^c)—嵌套循环或嵌套递归调用
  • O(c^n)—每一层有复杂的递归调用

8、大O总结

  • 比较算法效率
    • 描述增长的符号
    • 增长级别越低越好
    • 不依赖于机器或是专门的实现
  • 使用O
    • 描述增长订单
    • 渐进表示法
    • 上限值
    • 最差情况分析
第26天：20190724

学习时间：2小时
学习内容：MIT Lecture 12 视频+ PPT
学习收获：
1、在学习了各种搜索算法后，本节课讲解排序算法以及它们的复杂度，排序算法包括monkey sort、bubble sort、selection sort、merge sort
1.1、monkey sort：也叫bogo sort

  • 最好的情况：如果有序，复杂度为O(n)
  • 最差的情况：如果无序，很不幸，复杂度为无限的O(?)

1.2、bubble sort：复杂度为O(n2)——这里n是len(L)
1.3、selection sort：复杂度为O(n2)——这里n是len(L)
1.4、merge sort：复杂度为O(n log(n))——这里n是len(L)，运用递归思维，merge sort是最快的排序实现
2、课程来到尾声，我们在6.0001课堂都学到了啥？
2.1、核心议题

  • 用数据结构来表示知识
  • 迭代和递归作为计算隐喻
  • 程序和数据类型的抽象
  • 使用对象类和方法类组织和模块化系统
  • 不同的算法类，搜索和排序
  • 算法复杂度

2.2、课程6.0001概要——希望为学习者开启一条路径，像计算机科学家一样思考和行动。

  • 学习计算模式思维
  • 开始掌握计算问题解决的艺术
  • 让计算机做我们想让它做的事

2.3、计算机科学家做什么？

  • 他们从计算方面思考：抽象、算法、自动化执行
  • 正像阅读、写作和数学一样，计算思维正成为每一个受过良好教育的人所需要的基本技能。

2.4、计算思维的3A：

  • abstraction抽象
    • 选择正确的抽象
    • 同时在抽象的多层进行操作
    • 定义抽象层级之间的关系
  • automation自动化
    • 按照机械化我们的抽象来思考
    • 机械化是可能的——因为我们有精确的严格的符号和模型，并且因为有“机器”可以翻译我们的符号
  • algorithms算法
    • 用于描述自动化进程的语言
    • 也允许对细节进行抽象
    • 用于交流想法和进程的语言

2.5、计算思维的面貌

  • 这个问题有多难，我如何最好的解决它？
    • 理论上计算机科学对这些以及相关问题和答案给出确切含义
  • 递归的思考
    • 将一个看上去困难的问题分解形成一个我们知道如何解决的问题
    • 缩小、嵌入、转换、模拟
第27天：20190725

学习时间：2小时
学习内容：MIT6.0001 ps0
学习心得：
1、自学营虽然连滚带爬的走过，但都查阅的中文材料，现在开始老老实实啃英文，欠的债总是要还的，一个字一个字认真读。
2、ps0 : the goal of this programming exercise is to make sure your python and numpy installations are correct, and you have the ability to print out results, the ability to read input from a user at the console, and the ability to store values in a variable, so the program can access that value as needed.
3、Assignment：write a program that does the following in order:
1.Asks the user to enter a number “x”
2.Asks the user to enter a number”y”
3.Prints out number”x”, raised to the power”y”.
4.Pirnts out the log(base 2) of “x”.

4、代码：

1
2
3
4
5
6
import math

x = int(input("Enter number x: "))
y = int(input("Enter number y: "))
print("x**y = ",x**y)
print("log(x) = ",int(math.log(x,2)))

5、运行结果：
1564036604065_14_36_37__07_25_2019

6、7.11打卡时做过这部分的，现在能发现之前的错误并改之。另外虽然代码很简单，但是在完成的过程中，需要老老实实阅读很多hints，终于将英语用起来了。
7、pkgtest.py的运行测试是这样的：
1564037265052_14_47_43__07_25_2019

第28天：20190726

学习时间：2小时
学习内容：学习使用pythontutor，阅读style guide，练习pset1part A。
学习心得：
1、学习在线使用pythontutor，将自学营作业99乘法表的代码放进去，一步步查阅程序是如何实现的。
2、pset1 part A部分自己一条条列出了变量，也可以按照用户输入条件一个月一个月的自己在纸上进行计算，但到循环这部分，感觉还是写不出代码，和在自学营一样，需要借鉴同学的打卡，才能生成最终结果，是否已经形成了依赖心理？
3、代码
1564154672996_23_24_08__07_26_2019
4、运行结果
1564154727264_23_25_25__07_26_2019

第29天：20190727

学习时间：0.5小时
学习内容：继续pset1part B。
学习心得：
1、pset1 part B在partA基础上增加了一条每半年薪资按一个固定比例调高，只要在自增长的月份上增加一条，当月份数除6的余数为0时，年薪调整为原有年薪+年薪*调薪比例即可。另外初始变量需添加一个需要用户给定的每半年薪资增长率。
2、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 年度薪资
annual_salary = int(input("Enter your annual salary: "))
# 每月薪资存款比例
portion_saved = float(input("Enter the percent of your salary to save, as a decimal: "))
# 心仪房产总价
total_cost = int(input("Enter the cost of your dream home: "))
# 每半年薪资增长率
semi_annual_raise = float(input("Enter the semi-annual raise, as a decimal: "))
# 首付款比例
portion_down_payment = 0.25
# 首付款
down_payment = total_cost * portion_down_payment
# 存款年化收益率
r = 0.04
# 起始存款
current_savings = 0
# 起始月份
number_of_months = 1

while True:
    # 当月存款=起始存款+月薪*每月存款比例+投资回报
    current_savings = current_savings + annual_salary/12*portion_saved + current_savings*r/12
    if current_savings >= down_payment:
        print("Number of months: {}".format(number_of_months))
        break
    if number_of_months % 6 == 0:
        annual_salary += annual_salary * semi_annual_raise
    number_of_months += 1

3、运行结果
1564241501725_23_31_39__07_27_2019

第30天：20190729

学习时间：2小时
学习内容：重读《自学是门手艺》part.1.A-part.1.E.3+思考pset1partC。
学习心得：
1、前言，重视一切老生常谈，向真正做到的老生学习，听话照做就好。
2、习得自学能力的终极目标：有能力只靠阅读习得新技能。
3、运算和流程控制组成计算机程序的两个最基本成分。
4、数字值和字符串值的逻辑操作符包括：>、<、==、>=、<=、!=、in(属于)
5、数字的操作符有：+、-、、/、//、%、*
6、布尔值的运算操作符为：与、或、非，用and、or、not表示
7、任何一个逻辑表达式都会返回一个布尔值：False 或是 True
8、所有的工具都一样，效用取决于使用工具的人。学会使用工具固然重要，更重要的是自己的能力不断提高。
9、放慢速度耐心体会流程控制章节，将示例拷贝到pythontutor仔细理解流程的走向。

  • 只处理一种情况，用if …
  • 处理True/False两种情况，用if … else …
  • 处理多种情况，用if … elif … elif … else …
  • 迭代有序数据类型，用for … in …，如果需要处理没有break发生的情况，用for … else …
  • 其它循环，用while …
  • 与循环相关的语句还有continue、break、pass

10、MIT pset1partC部分，知道是要用二分搜索查找最佳存款比例，头脑中思路还是不清晰，另外语言的理解上也有不清晰的地方，忍住了没有参考同学们的答案（好像有点养成习惯了），自己再思考几天，反复学习理解一下二分搜索的代码示例，争取自己做出答案。
11、另外感谢@陪练-QueenieQ的热心答疑，前两天的打卡文内图片已经用iPic上传图片至图床，可以有链接看到图片了。