python数据结构与算法分析（二）

2023-03-12 23:01| 来源: 网络整理| 查看: 265

一.何谓算法分析 1.案例：计算前n个数之和 2.大O记法 3.案例：异序词检测二.数据结构性能 1.列表 2.字典一.何谓算法分析 1.案例：计算前n个数之和

a.第一种做法

def sumOFN2(n): theSum = 0 for i in range(1, n+1): theSum = theSum+i return theSum

运行所需时间（运用time模块里面的time函数）

import time def sumOFN2(n): start = time.time() theSum = 0 for i in range(1, n+1): theSum = theSum+i end = time.time() return theSum, end-start for i in range(5): print("Sum is %d required %10.7f seconds" % sumOFN2(1000000))

结果

b.第二种方法

def foo(tom): fred = 0 for bill in range(1,tom+1): barney = bill fred = fred + barney return fred '''其实就是把i重新拆分开两个变量'''

时间

import time def foo(tom): start = time.time() fred = 0 for bill in range(1,tom+1): barney = bill fred = fred + barney end = time.time() return fred, end - start for i in range(5): print("Sum is %d required %10.7f seconds" % foo(1000000))

结果

c.不用循环

时间（时间很少，结果反馈不出来）

def sumOFN3(n): start = time.time() m = (n * (n + 1)) / 2 end = time.time() return m, end - start for i in range(5): print("Sum is %d required %10.7f seconds" % sumOFN3(100000000)) 2.大O记法

我们引入时间复杂度的概念：用于评估运行效率的一个式子

有最好情况，最坏情况和平均情况之分，我们一般考虑最坏情况

O是啥？（时间复杂度是啥？）

假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度。

O(f(n))的判断

循环多少次，就输出运行次数n就有多少次方

强调的是一个大概值，不需要精确

算法复杂度判断

既然提到时间复杂度，我们不妨也提一下空间复杂度

空间复杂度：

用来评估算法占用空间的式子

3.案例：异序词检测如果一个字符串只是重排了另一个字符串的字符，那么这个字符串就是另一个的异序词，比如 heart 与 earth ，以及 python 与 typhon 。为了简化问题，假设要检查的两个字符串长度相同，并且都是由26 个英文字母的小写形式组成的。我们的目标是编写一个布尔函数，它接受两个字符串，并能判断它们是否为异序词。方案 1 ：清点法 def anagramSolution1(s1, s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and stillOK: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]: found = True else: pos2 = pos2 + 1 if found: alist[pos2] = None else: stillOK = False pos1 = pos1 + 1 return stillOK 先要将第 2 个字符串转换成列表。在字符列表中检查第 1 个字符串中的每个字符，如果找到了，就替换掉。访问次数：

即O(n^2) 方案2：排序法 def anagramSolution2(s1, s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() pos = 0 matches = True while pos < len(s1) and matches: if alist1[pos] == alist2[pos]: pos = pos + 1 else: matches = False return matches '''先把字符串做成列表，进行排序，然后在列表中一个元素一个元素对照'''

sort方法需要遍历一遍列表，比较n个字符，调用两次sort的O为O(n^2)

方案3：计数法

def anagramSolution3(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

【本文地址】

公司简介

联系我们