《Python 数据结构与算法分析》笔记

Problem Solving with Algorithms and Data Structures Using Python - Second Edition

https://www.bilibili.com/video/BV1n5411h7Ys?from=search&seid=15590717491486760043

[toc]

第 1 章 导论

1.4 Python 基础

• Python 列表提供的方法

* HINT：结合 list 和 range 来初始化列表

• Python 字符串提供的方法

• split 在处理数据的时候非常有用。split 接受一个字符串,并且返回一个由分隔字符作为分割点的字符串列表。

  'David'.split('v')

• 在本例中,v 就是分割点。如果没有提供分隔字符,那么 split 方法将会寻找如制表符、换行符和空格等空白字符。

• 集 (set)是由零个或多个不可修改的 Python 数据对象组成的无序集合。集不允许重复元素,并且写成由花括号包含、以逗号分隔的一系列值。空集由 set() 来表示。集是异构的,并且可以通过下面的方法赋给变量。

• 假设有两个Fraction 对象,f1 和 f2 。只有在它们是同一个对象的引用时, f1 == f2 才为 True 。这被称为浅相等。深相等 ——根据值来判断相等。

• Python 字典提供的方法

• 格式化字符串

print("%s is %d years old." % (aName, age))

• 格式化字符串可用的类型声明

• 列表可以通过使用迭代结构和分支结构来创建。这种方式被称为列表解析式

sqlist = [x*x for x in range(1,11)]

• try, except; raise也可以触发运行时的异常

if anumber < 0: 
	raise RuntimeError("You can't use a negative number") 
else: 
	print(math.sqrt(anumber))

第 2 章 算法分析

2.2 何谓算法分析

2.2.1 大 O 记法

• O(log2n)

2.2.2 异序词检测

• 清点法 O(n^2^)

def reverse_word(str1, str2):

    if len(str1) != len(str2):
        return False

    for c1 in str1:
        for c2 in str2:
            if c1 == c2 and c1 != '#':
                # 核心思想是代替，把对应位置如果一样就换成 '#'
                # 所以使用的是 replace ！
                str1 = str1.replace(c1, '#')
                str2 = str2.replace(c2, '#')
                # str1 = '#'
                # str2 = '#'
            #return False

    for c1 in str1:
        if c1 != '#':
           return False

    for c2 in str2:
        if c2 != '#':
            return False

    return True

if __name__ == "__main__":
    str1 = "python"
    str2 = "typhon"
    print(reverse_word(str1, str2))

• 计数法 O(n)

lst1 = [0] * 26
lst2 = [0] * 26
str1 = 'earth'

for c in str1:
    # 计算出字母相对位置
    idx = ord(c) - ord('a')
    # 找出此时在列表中的绝对位置，使 count 指向此处s
    count = lst1[idx]
    # count 的值增加 1
    count += 1
    # 把此时列表中对应位置的出现次数更新
    lst1[idx] = count

str2 = 'heart'

for c in str2:
    # 计算出字母相对位置
    idx = ord(c) - ord('a')
    # 找出此时在列表中的绝对位置，使 count 指向此处s
    count = lst2[idx]
    # count 的值增加 1
    count += 1
    # 把此时列表中对应位置的出现次数更新
    lst2[idx] = count

# 直接判断 lst1 == lst2 也可以
for i in range(0,len(lst1)):
    if lst1[i] != lst2[i]:
        break

if i == len(lst1) - 1:
     print('True')
else:
    print('False')

• 该算法执行时间是线性的,它还是要用额外的空间来存储计数器。也就是说, 这个算法用空间换来了时间。
• 单词统计字符次数可以考虑用字典。

2.3 Python 数据结构的性能

2.3.1 列表

• 一般来说，创建列表的操作时间对比，列表表达式([i for i in range(xxx)]) < list(range(xxx)) < append(i) 追加 < 连接(l += [i])
• Python 列表操作的大 O 效率(以底层数组实现为例)

操作	大 O 效率
索引	O(1)
索引赋值	O(1)
追加	O(1)
pop()	O(1)
pop(i)	O(n)
insert(i, item)	O(n)
删除	O(n)
遍历	O(n)
包含	O(n)
切片	O(k)
删除切片	O(n)
设置切片	O(n + k)
反转	O(n)
连接	O(k)
排序	O(nlogn)
乘法	O(nk)

2.3.2 字典

• Python 字典操作的大 O 效率

操作	大 O 效率
复制	O(n)
取值	O(1)
赋值	O(1)
删除	O(1)
包含	O(1)
遍历	O(n)

• 在某些特殊情况下,包含、取值、赋值等操作的时间复杂度可能变成O(n)。

第三章 基本数据结构

3.2 何谓线性数据结构

• 一旦某个元素被添加进来，它与前后元素的相对位置将保持不变。

3.3 栈

3.3.3 用 Python 实现栈

• 假设列表尾部是栈的顶端

赏

谢谢你请我吃糖果

支付宝

微信