Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

685-杜同学

发表文章数:68

首页 » 数据结构 » 正文

数据结构虐我千万遍,我依然待它如初恋。


首先引出一个问题:

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

可以看到对于同样问题使用不同解法(也称算法)时间上的差距。这里用了time模块的time.time()函数来计算时间差。

算法是独立存在的一种解决问题的方法和思想。

那么如何衡量一个算法的好坏呢?

时间复杂度的几条基本计算规则

  1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
  2. 顺序结构,时间复杂度按加法进行计算
  3. 循环结构,时间复杂度按乘法进行计算
  4. 分支结构,时间复杂度取最大值
  5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
  6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

​​​​​​​Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

那么我们分析一下刚才我们写的两段程序的时间复杂度

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

 

timeit模块

除了time模块Python还内置了timeit模块来测试Python代码的执行速度

class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)

stmt参数是要测试的代码语句(statment)

setup参数是运行代码时需要的设置

timer参数是一个定时器函数,与平台有关。

timeit.Timer.timeit(number=1000000)

Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数,默认为1000000次。方法返回执行代码的平均耗时,一个float类型的秒数。

list的操作测试

from timeit import timeit

def test1():
   l = []
   for i in range(1000):
      l = l + [i]
def test2():
   l = []
   for i in range(1000):
      l.append(i)
def test3():
   l = [i for i in range(1000)]
def test4():
   l = list(range(1000))

from timeit import Timer

t1 = Timer("test1()", "from __main__ import test1")
print("+ ",t1.timeit(number=1000), "seconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "seconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "seconds")

# ('+ ', 1.7890608310699463, 'seconds')
# ('append ', 0.13796091079711914, 'seconds')
# ('comprehension ', 0.05671119689941406, 'seconds')
# ('list range ', 0.014147043228149414, 'seconds')

pop操作测试

x = range(2000000)
pop_zero = Timer("x.pop(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
x = range(2000000)
pop_end = Timer("x.pop()","from __main__ import x")
print("pop_end ",pop_end.timeit(number=1000), "seconds")

# ('pop_zero ', 1.9101738929748535, 'seconds')
# ('pop_end ', 0.00023603439331054688, 'seconds')

测试pop操作:从结果可以看出,pop最后一个元素的效率远远高于pop第一个元素

数据结构

我们想要存储一个班级的学生,学生有name姓名、age年龄和homtown家乡

我们可以用多种不同的数据结构来实现

# 使用列表+元组存储
[
    ('Tom',24,'Beijing'),
    ('Jerry',23,'Shanghai'),
    ('Merry',24,'shenyang'),
]

# 使用列表加字典存储
[
    {
        'name':'Tom',
        'age':24,
        'hometown':'Beijing',
    },
]

# 使用字典加字典存储
{
    'Tom':{'age':24,'hometown':'Beijing'},
    'Jerry':{'age':23,'hometown':'Shanghai'},
    'Merry':{'age':24,'hometown':'Shenyang'}
}

但当我们要进行查找操作时,第一种需要for stu in students: stu[0] == 'Merry' 第二种需要for stu in students: stu[‘name’] == 'Merry',这两种的效率都为O(n),而第三种直接student['Merry'],为O(1)

所以数据结构会对时间造成影响

Python中内置的数据结构

list内置操作的时间复杂度

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

dict内置操作的时间复杂度

Python数据结构与算法(一)——数据结构与算法基础、时间复杂度、列表与字典的时间复杂度

算法与数据结构的区别

程序 = 数据结构 + 算法

总结:算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体

抽象数据类型(Abstract Data Type)

抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起,进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开,使它们相互独立。

最常用的数据运算有五种:

  • 插入
  • 删除
  • 修改
  • 查找
  • 排序

 

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录