文档章节

MIT6.00.1X 计算机科学和PYTHON编程导论 第五周

ElfenS
 ElfenS
发布于 2016/07/19 15:48
字数 1234
阅读 21
收藏 1

第九讲    效率和增长量级

    我们的首要目标就是让代码正常运行,能够计算出正确的答案。尽管如此,我们还是希望代码能够达到第二个目标,即高效地进行计算。通常而言,第一个目标更加重要,但有时候第二个目标也十分重要,同时我们需要平衡计算的复杂度和理解代码的复杂度。

   复杂度 :

        我们假设一个基本步骤就是一个操作,而这个操作的用时总是一样的,之后我们只需专注于数清楚计算函数时所执行的基本步骤即可。测量复杂度我们只关心增幅最快的项,并且忽略系数。

    例:

def f(x):
    for i in range(1000):
        ans = i
    for i in range(x):
        ans += 1
    for i in range(x):
        for j in range(x):
            ans += 1
#这一段代码的步骤总数为1000+2x+2x^2,对于其复杂度我们只关心增长最快的项即2x^2,
#同时我们不关心系数就得到该函数的复杂度x^2。对于复杂度我们使用大写的O表示,
#则该函数的复杂度表示为O(n^2)

       常见的复杂度(耗时,由低到高):

        O(1)          常数时间算法,运算时间不随运算量的增加而增加

        O(log n)    对数时间算法

        O(n)          线性时间算法

        O(n * log n)    对数-线性时间算法

        O(n^c)        多项式时间算法

        O(c^n)        指数时间算法

# 对数时间算法
def intToStr(i):
    digits = '0123456789'
    if i == 0:
        return '0'
    result = ''
    while i > 0:
        result = digits[i%10] + result
    i = i/10
    return result

# 运算步骤 log10(i) 复杂度 O(log(i))
# 线性时间算法
def addDigits(s):
    val = 0
    for c in s:
    val += int(c)
    return val
#总步骤 len(s)  复杂度O(len(s))
def fact(n):
    if n == 1:
        return 1
    else:
        return n*fact(n-1)

#总步骤 n  复杂度O(n)
# 多项式时间算法
def isSubset(L1, L2):
    for e1 in L1:?
        matched = False
        for e2 in L2:
            if e1 == e2:
                matched = True
                break
        if not matched:
            return False
    return True

# 总步骤为 len(L1)*len(L2)   这里我们只考虑最坏的情况即 len(L1) == len(L2) 
# 所以这个算法的复杂度为 O(len(L1)^2)

def intersect(L1, L2):
    tmp = []
    for e1 in L1:
        for e2 in L2:
            if e1 == e2:
                tmp.append(e1)
    res = []
    for e in tmp:
        if not(e in res):
            res.append(e)
    return res
# 总步骤为 len(L1)*len(L2) + len(L1)  我们只关心增长最快的项, 
# 所以这个算法的复杂度为O(len(L1)^2)
# 指数时间算法
def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]] #list of empty list
    smaller = genSubsets(L[:-1])
    # get all subsets without last element
    extra = L[-1:]
    # create a list of just last element
    new = []
    for small in smaller:
        new.append(small+extra)
    # for all smaller solutions, add one with last element
    return smaller+new
    # combine those with last element and those without

# 总步骤为 2^(n-1)+..+...+2^0, 所以该算法的复杂度为O(2^n) 

第十讲    内存和查找

        我们可以同过间接索引的办法来查找需要的数据。

        一般的对于无序列表的查找,时间复杂度为O(n),而有序列表可通过二分查找将时间复杂度缩短为O(log(n)),所以我们可以通过对列表排序,使其变成有序的,再使用二分查找,只要我们找到一种排序算法使得 sort(L) + log(len(L)) < len(L) 则运算效率将会更高,而且对于多次查找,效率的提升就更加明显了。

# 选择排序
def selSort(L):
    for i in range(len(L) - 1):
        minIndx = i
        minVal= L[i]
        j = i + 1
        while j < len(L):
            if minVal > L[j]:
                minIndx = j
                minVal= L[j]
            j += 1
        temp = L[i]
        L[i] = L[minIndx]
        L[minIndx] = temp

# 这里选择排序的时间复杂度为 O(len(L)^2),显然选择排序的效率并不高,
# 我们需要更好的排序方法
# 归并排序
# 将列表分为两部分,分别排序,然后将两个列表合并
def merge(left, right, compare):
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

import operator
def mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)
# merge的复杂度为 O(len(L))  mergesort 的复杂度为 O(len(L) * log(len(L)))
# 简化为 O(n*log(n))  归并排序相比于选择排序效率提高了很多,这样的效率我们可以接受

    hash:

        哈希的思想如下。给定一个键,比如,它指向了一个字典的一个元素。一个哈希函数会将这个键转换为一个整数,然后它用这个整数来检索列表。哈希函数可以让我们查找东西,这个查找过程的用时几乎独立于字典的规模。

© 著作权归作者所有

共有 人打赏支持
ElfenS
粉丝 1
博文 6
码字总数 7791
作品 0
万州
程序员
私信 提问
福利 | Python专场竞技,这些书给你加把力!

端午节将至,各地龙舟备战竞技,粽子部队也整装待发。小编掐指一算,这种热闹的时节,是时候展现真正的技(fu)术(li)了! (“Python号”龙舟闪亮登场!) Python作为当下最流行的编程语言...

2018/06/15
0
0
良心推荐:一份20周学习计算机科学的经验贴(附资源)

雷锋网按:这里是,油管Artificial Intelligence Education专栏,原作者Siraj Raval授权雷锋字幕组编译。 原标题 Computer Science Curriculum 翻译 | 王飞 整理 | 凡江 这是一份五个月(20个...

雷锋字幕组
2018/05/08
0
0
学习周记3:2019.3.4-2019.3.10(模板)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/BeerBread134/article/details/87908291 前言 这学期几乎全是硬核的算法/程序课,为了督促自己认真学习,我将...

陶晨毅
02/24
0
0
学习周记4:2019.3.11-2019.3.17(模板)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/BeerBread134/article/details/88113035 前言 这学期几乎全是硬核的算法/程序课,为了督促自己认真学习,我将...

陶晨毅
03/04
0
0
学习周记6:2019.3.25-2019.3.31

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/BeerBread134/article/details/88785051 前言 这学期几乎全是硬核的算法/程序课,为了督促自己认真学习,我将...

陶晨毅
03/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式事务解决方案框架(LCN)

什么是XA接口 XA是一个分布式事务协议,由Tuxedo提出。XA中大致分为两部分:事务管理器和本地资源管理器。其中本地资源管理器往往由数据库实现,比如Oracle、DB2这些商业数据库都实现了XA接口...

群星纪元
10分钟前
0
0
linux 操作系统 常用命令和软件安装

1.系统时间更新 ntpdate time.windows.com 2.传送文件 rsync -av /home/data/a.dat -e ssh root@192.168.0.100:/home 3.传送文件夹 scp -r /home/data root@192.168.0.100:/home 4.JDK安装 ......

WJtiny
32分钟前
0
0
pg_lightool基于basebackup的单表恢复和块恢复

开源软件pg_lightool,实现了基于wal日志的块恢复。详情参见博客:https://my.oschina.net/lcc1990/blog/1931485。由于wal日志中FPW的不确定性,它不能作为一个数据库恢复的解决方案。目前对...

movead
40分钟前
2
0
对比剖析Swarm Kubernetes Marathon编排引擎

Docker Native Orchestration 基本结构 Docker Engine 1.12 集成了原生的编排引擎,用以替换了之前独立的Docker Swarm项目。Docker原生集群(Swarm)同时包括了(Docker Engine \/ Daemons)...

Linux就该这么学
41分钟前
2
0
Mybatis的结果集处理

此时我们已经可以把整段的SQL语句取出,但还并没有在数据库中去执行,我们可以先来分析一下配置文件中SQL语句执行后的结果集是如何处理的。 Mybatis会将结果集按照映射配置文件中定义的映射规...

算法之名
53分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部