?
?
大O表示法
?
?问题规模
?
?抓大头，数量级
?
?
?决定运行时间的不仅是问题规模，还跟工况有关，平均状况
常见的七种
?
?
?
P10 变位词判断问题
?
问题：
解法1
解法2：先排序后比较
?
?
def paiXU(s1,s2):
a=list(s1)
b=list(s2)
a.sort()
b.sort()
pos=0
matches=True
while pos<len(s1) and matches:
if a[pos] == b[pos]:
pos=pos+1
print('jia1')
else:
matches=False
return matches
print(paiXU('wangc','thonpy'))
?P11 变为词的判断问题
解法3，暴力法
?
?
?解法4
?
?
def solution4(s1,s2):
c1=[0]*26;
c2=[0]*26;
for i in range(len(s1)):
pos=ord(s1[i])-ord('a')
c1[pos]=c1[pos]+1
for i in range(len(s2)):
pos=ord(s2[i])-ord('a')
c2[pos]=c2[pos]+1
j=0
stillOk=True
while j<26 and stillOk:
if c1[j]==c2[j]:
j=j+1
else:
stillOk=False
return stillOk
print(solution4('wangc','pleap'))
?P12 Python数据类型的性能上
?
?
?
?
?
?P12 Python的数据类型下
?
?
?
?
?这一节课没有动手
P14什么是线性结构
?
?四种：栈、队列、列表、双端队列
?P15栈抽象数据类型及Python实现
?加入移除的一段成为栈顶
?
?
??长按即可出现列表
?
?
?
?
?调用接口即可
?列表和字体是最常见的，
使用列表来实现栈
?
?
?
?
?
?
?
?P16栈的应用：简单括号匹配
?