MIT600SC笔记8&9


第八课:Efficiency and Order of Growth

效率跟clever coding无关,也没有trick。在于选择正确的算法。

Efficiency is about algorithm.

(将问题)Reduce it to a previously solved problem.

考虑效率问题的两个维度: Space& Time 内存和运行时间,专注于时间

为什么不考虑/衡量Computational complexity计算复杂度(程序在电脑上运行的时间),不稳定的相关因素:1)Speed of machine,2) cleverness of python implementation, 3)depends upon input

更抽象的方法:Count the number of basic steps. Time N -> N 第一个N对应输入的size,第二个对应计算输入所需要的steps(step是消耗恒定时间的operation,所以steps是恒量)

random access machine(RAM)–> Sequential(在这个计算机模型中一次只能运行一个任务)–> 并且我们假定access memory的时间是恒定的。

Best Case: Algorithm进行linear search,第一个查找的就是需要找到的。通常不考虑这种情况

Worst Case:结果根本不存在。根据墨菲法则,复杂度分析总是专注于最坏的情况。作用:提供Upper bound,经常发生

Expected average Case:结果在输入的数据的中间位置, 不可假设,涉及很多因素,因此通常不重点考虑这个情况。

/*我发现用php写课程里的东西有点顶不住,还是换了python的IDE来写,不过贴的代码没缩进比较要命*/

def f(n):
assert n >= 0
answer = 1
while n > 1:
answer *= n
n -= 1
return answer

上面的这段代码分以下几步:1)assertion, 2)assignment,  3)每次循环3 step,  4)return

算法总共的步数是:2+3*n+1,真正值得关注的是3*n的部分,growth with respect to size of input, 更进一步甚至可以忽略3*n中的3,只关注n,运用模型asymptotic growth(描述达到输入的size限制后复杂度如何增长)

复杂度符号 Big Oh notation—> (O)n

模型的目的是给我们upper bond —>F(x) is  O(x平方)

Function F grows no faster than the quadratic polynomial x的平方

O(1) – constant (意思是独立于input size所需要的时间);O(log n)对数增长;O(n) 线性;O(n log n)–log linear;O(n的c次方)- polynomial;O(c的n次方)–幂

幂的运算太庞大,没人会用这种算法。遇到原则上要用这种算法的问题,我们解决这些问题的近似问题,或者用某些tricks避开已知的最坏的情况。

可能的话不要用比log linear更复杂的算法

def h(x):
assert type(x) == int and x >=0
answer = 0
s = str(x)
for c in s:
answer += int(c)
return answer

O(n) where n is #digits in S log 10 x(没办法输入数学符号的路过)这样会在输入方面扩大算法的复杂度,不是取决于S,而是取决于x

第九课:Memory and Search Methods

大致的说无论32还是64位,一个int总是根据语言的需要占据相同数量的空间。

假设整数占据4 units of memory—>location of L[i]?—>start of the list(start+4*i)–可以假设相同类型的元素占据相同大小的空间

但是python中的list并不总是包含相同类型的元素,Linked List: every element of the list is a pointer to the next element&value—>在linked list中,找到L[i]要经过i步,O(i), 这样的话python中查找元素的时间就不是log i而是i.

Python使用的方法是indirection,list当中的每个元素都指向list所在的内存section外部, 这样就可以无视object的size用恒定的时间找到元素。

不能使用太多层级的indirection, 某些model中indirection因为pointer和value之间相隔太远干扰cache会导致效率急剧下降。大部分情况下效率很高高度推荐。

Binary Search基于List is sorted的假设。是否要1)sort L–O(?);2)use binary search–O(log(len(L)))

我们总是可以使用linear search,O(L),所以要比较O(?)+O(log(len(L)))跟O(L)的大小,没有任何一种算法可以实现前者相加比后者小,因为要sort必然要查看list当中的每个元素至少一次。O(?)的下限就是O(L)。

Amortized Complexity 如果sort一次然后用来搜索很多次,可以把sort的成本一点点的分配到后面的search上。

If we plan on K searches, is sort(L)+K*log(len(l)) < K * len(L). 关键在于sort的复杂度和K的次数。

不能用来sort的方法:Bubble sort, Selection sort(establishing & maintaining invariant, 这里的invariant是一个pointer,用来分割list为prefix&suffix,Inv = prefix is always sorted, 从prefix初始为0到suffix为0,例如初始4,2,3;第一步2,4,3;第二步2,3,4)

例子:

这个的复杂度:n=len(L), 第一次查看n个元素,第二次n-1,依此类推,复杂度为 n的平方/2,我们所能接受的最大不超过n*log(n),所以不推荐

有人提出根据Divide&Conquer法则对以上的方法进行优化:1)选择一个threshold input size, no, 这将是smallest problem,  2)how many instances at each division, 3)运用算法combine sub-solutions

先看第三步:单次融合的方法,假设有两个sorted list,[1,5,12,18,19,20], [2,3,4,17], 合并的方法,比较两个数列的第一个元素,选择1;然后比较5和2,选则2;然后3和5……copy的复杂度 O(len(L)), 比较的复杂度上限O(len(L))。要融合的次数是O(log(len(L))),所以整个merge sort的复杂度是n log(n).

#这段代码不贴了,我的IDE是python3的,lambda的用法是python2的,我不知道怎么改



发表评论

电子邮件地址不会被公开。 必填项已用*标注