首页 > 分享 > 时间复杂度和大O表示法&&数据结构引入

时间复杂度和大O表示法&&数据结构引入

花匠小妙招
2024-12-15 11:39

Python数据结构与算法学习日记（一）

一、时间复杂度（T）与大O表示法

如果a+b+c=1000, a^2 + b^2 = c^2 , (a,b,c为自然数)，如何求出所有a,b,c的组合？

import time #start_time = time.time() for a = range(0,1001):for b = range(0,1001);for c = range(0,1001);if a+b+c=1000 and a**2+b**2=c**2：print("a,b,c:%d,%d,%d" % (a,b,c)) #end_time = time.time() #print("time:%d" % (end_time - start_time)) #print("finished") # T = 1000 * 1000 * 1000 * 2 # T(n) = n^3 * 2 , n是数据规模 # T(n) = n^3 12345678910111213

运行结果： time : 244 (s)

改进：（利用c=1000-a-b）

import time #start_time = time.time() for a = range(0,1001):for b = range(0,1001);c = 1000-a-bif a**2+b**2=c**2：print("a,b,c:%d,%d,%d" % (a,b,c)) #end_time = time.time() #print("time:%d" % (end_time - start_time)) #print("finished") # T(n) = n * n * (1 + max(1,0)) 1234567891011

运行结果：time : 1 (s)

用基本运算数量表征算法优劣

大O表示法就是指T（n）的渐近函数

二、最坏时间复杂度和计算规则

计算规则：

基本操作：只有常数项，认为其时间复杂度为O（1）；顺序结构：时间复杂度按加法计算；循环结构：时间复杂度按乘法计算；分支结构：时间复杂度取最大值；判断一个算法的效率时，往往只需要关注操作数量的最高次项, 其他次要项或常数项可以忽略；在没有特殊说明时，我们所分析的时间复杂度都是最坏时间复杂度。

常见时间复杂度与大小关系

执行次数函数举例阶非正式术语12O(1)常数阶2n+3O(n)线性阶3n^2+2n+1O(n^2）平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(n*logn）nlogn阶6n^3+2n2+3n+4O(n^3)立方阶2^nO(2n)指数阶

在这里插入图片描述
所消耗的时间从小到大

O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

三、代码执行时间和计时模块timeit

timeit模块可以用来测试一小段Python代码的的执行速度

class timeit.Timer(stmt=‘pass’,setup=‘pass’,timer=<timer funtion’>)
timeit.Timer.timeit(number = 100000)

stmt：用于传入要测试时间的代码，可以直接接受字符串的表达式，也可以接受单个变量，也可以接受函数。传入函数时要把函数申明在当前文件中，然后在 stmt = ‘func()’ 执行函数，然后使用 setup = ‘from main import func’

setup：传入stmt的运行环境，比如stmt中使用到的参数、变量，要导入的模块等。可以写一行语句，也可以写多行语句，写多行语句时要用分号；隔开语句。

number：要测试的代码的运行次数，默认100000次，对于耗时的代码，运行太多次会比较慢，此时建议自己修改一下运行次数

timer：是一个定时器函数，与平台有关

四、列表的创建方法与利用timeit测试时间

基本语法创建

a = [30,40,50,'gene'] a = [] #创建空列表，通过a.append()加入元素 123' List( )创建

a = list() #创建空列表对象 a = list('gene') # a = ['g','e','n','e'] a = list(range(5)) # a = [0,1,2,3,4] 123' Range 创建整数列表（用得很多）

# range([start,] end [,step]) start缺省值为0，step为1 a = list(range(3,10,2)) # a = [3,5,7,9] a = list(range(10,3,-1)) # a = [10,9,8,7,6,5,4] 123' 推导式生成列表

a = [x*2 for x in range(5)] # a = [0,2,4,6,8] a = [x*2 for x in range(100) if x%9 == 0] # a=[0,18,36,54,72,90,108,126,144,162,180,198] 12'

测试上述方式的运行时间

def test1():li = []for i in range(10000):li.append(i) def test2():li = []for i in range(10000):li += [i] #+操作效率很低，一般用li.extend() def test3():li = [i for i in range(10000)] def test4():li = list(range(10000)) timer1 = Timer("test1()","from _main_ import test1") print("append:",timer1.timeit(1000)) timer2 = Timer("test2()","from _main_ import test2") print("+= :",timer2.timeit(1000)) timer3 = Timer("test3()","from _main_ import test3") print("[i for i in range]:",timer3.timeit(1000)) timer4 = Timer("test4()","from _main_ import test4") print("list(range())",timer1.timeit(1000))

123456789101112131415161718192021222324252627

五、Python 列表与字典操作的时间复杂度

List

操作操作说明时间复杂度index(value)查找list某个元素的索引O(1)a = index(value)索引赋值O(1)append(value)队尾添加O(1)pop()队尾删除O(1)pop(index)根据索引删除某个元素O(n)insert(index, value)根据索引插入某个元素O(n) iterrationsearch(in)列表搜索（其实就是in关键字）O(n)slice [x:y]切片, 获取x, y为O(1), 获取x,y 中间的值为O(k)O(k)del slice [x:y]删除切片，删除切片后数据需要重新移动/合并O(n)reverse列表反转O(n)sort排序O(nlogn)

Dict

操作操作说明时间复杂度copy复制O(n)get(value)获取O(1)set(value)修改O(1)delete(value)删除O(1)search(value)字典搜索O(1)iterration(value)字典迭代O(n)

六、数据结构引入

先置知识：
元组：不可变序列，一旦创建不能改变（列表是可变序列）

#元组的创建 #1. 直接创建 a = (10,20,30) #or a = 10,20,30 没区别 b = (10,) #只有一个的时候，要加逗号，不然type是数，不是元组 #2. 通过tuple创建（通常用于把其他可迭代对象转换成元组） a = tuple() #创建空元组对象 b = tuple("abcd") # b = ('a','b','c','d') c = tuple(range(3)) # c = (0,1,2) d = tuple([2,3,4]) # d = (2,3,4) del b # 删除元组b 12345678910'

字典：“键值对”的无序可变序列（键和值是一起的，成对出现，通过键，找值）; 列表可以通过下标数字找到对应的对象，这和字典通过键找值本质上是一样的 1

a = {'name':'gene','age':18,'job':'programmer'} a.get('name') # a = 'gaoqi' #键是任意的不可变数据，如整数、浮点数、字符串、元组，但是列表、字典、集合这些可变对象，不能作为键。并且键不可重复。 #字典的创建 #1. 通过{}创建 a = {} #空的字典对象 a = {'name':'gene','age':18,'job':'programmer'，'dd':[2,3,4]} #2. 通过dict()创建 b = {} #空的字典对象 b = dict(name="gene",age=18) #3. 通过zip()创建 k = ['name','age','job'] v = ['gene','22','student'] d = dict(zip(k,v)) # d = {'name':'gene','age':'22','job':'student'} #4. 利用fromkeys创建值为空的键（略） 123456789101112131415

数据的组织方式不同，时间复杂度不同，这就是数据结构的概念，数据结构是对基本数据的封装。

举个例子：

#现要储存班级内的name age hometown #1. 利用列表+元组储存 [("gene",22,"hangzhou"),("crystal",23,"beijing"),("sam",24,"wuhan") ] #查找数据时 for stu in stus:if stu(0) == "gene": ~~~ # T(n)= O(n) #2. 利用字典储存 {"gene":{"age":22,"hometome":"hangzhou"} } #抽象数据类型（ADT）：把数据结构和它支持的方法放到一起，比如对于上面第一种储存方式 class stus(object):def adds(self)def popdef sort

12345678910111213141516171819202122232425