Python数据结构与算法(一)—– 算法效率

756-周同学

发表文章数:47

热门标签

,
首页 » 数据结构 » 正文

一. 引入

先来看一道题:
如果a+b+c=1000, 且a2+b2=c^2(a,b,c为自然数),如何求出所有a,b,c可能的组合?
(1) 枚举法

import time

start_time = time.time()
for a in range(0,1001):
    for b in range(0,1001):
        for c in range(1,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

改进代码

import time

start_time = time.time()
for a in range(0,1001):
    for b in range(0,1001):
        c = 1000-a-b
        if 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))=n^2
  1. 算法的概念:是独立存在的一种解决问题的方法和思想
  2. 算法的五大特征:
    (1)输入:算法具有0个或多个输入
    (2)输出:至少有一个或多个输出
    (3)有穷性:在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内执行
    (4)确切性:每一步有确切的含义
    (5)可行性:每一步是可行的

二 . 算法效率

时间复杂度和“大O计法”
时间复杂度:T(n) = n^3 * 2
大O计法:不用分析很精确 T(n) = n^3

  1. 最坏时间复杂度:
[1,2,4,8,6,5,3,1]排序 n^2
[1,2,3,4,5] for i in ls:  n

(1) 最优时间复杂度:价值不大,没有提供什么有用信息
(2)最坏时间复杂度:提供了一种保证
(3)平均时间复杂度:是对算法的一个全面评价,没有提供保证
因此,主要关注最坏时间复杂度,然后最优时间敷在读
2. 时间复杂度的几条基本计算规则:
(1) 基本操作,即只有常数项
(2)顺序结构,按照加法进行计算
(3)循环结构,按照乘法进行计算
(4)分支结构,时间复杂度取最大值
(5)判断一个算法的效率时,往往只需要关注操作量的最高项次,其他次要项和常数项可以忽略
(6)在没有特殊说明时,我们通常分析最坏时间复杂度
3. 常见时间复杂度:
(1)12 O(1) 常数阶
(2) 2n+1 O(n) 线性阶
(3)3n^2 O(n2) 平方阶
(4)5logn. O(long) 对数阶
(5)2n+3nlogn+19 O(n*logn) nlogn阶
(6) 6n
3+2n2+3n+4 O(n3) 立方阶
(7)2n O(2n) 指数阶
关系:
O(1)<O(n*logn)<O(n) <O(n2)<(n3)<O(2n)<O(n!)<O(nn)

三. Python内置类型性能分析

1. timeit模块

可以用来测试一小段代码的运行速度
class time.Timer(stmt=‘pass’,setup=‘pass’,time=)
time.Timer.timeit(n=1000000)
number参数时测试代码时的测试次数

  1. 测算list
from timeit import Timer

#li1 = [1,2]
#li2 = [23,5]
#li = li1 +li2
#li = [i for i in range(10000)]
#li = list[range(10000)]

def test1():
    li = []
    for i in range(10000):
        li.append(i)

def test2():
    li = []
    for i in range(10000):
        li += [i]

def test3():
    li = [i for i in range(10000)]

def test4():
    li = list(range(10000))

def test5():
    li = []
    for i in range(10000):
        li.extend([i])

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 from i in range]:',timer3.timeit(1000))

timer4 = Timer('test4()','from __main__ import test4')
print('list(range()):',timer4.timeit(1000))

timer5 = Timer('test5()','from __main__ import test5')
print('list(range()):',timer5.timeit(1000))
##最快的是timer5

def test6():
    li = []
    for i in range(10000):
        li.append(i) ##从列表尾添加
        
def test7():
    li = []
    for i in range(10000):
        li.insert(0,i) ##从列表头添加
        
timer6 = Timer('test6()','from __main__ import test6')
print('append:',timer6.timeit(1000))

timer7 = Timer('test7()','from __main__ import test5')
print('list(extend:',timer7.timeit(1000))
##对头添加比对尾添加慢
  1. list 内置时间复杂度
  2. dict内置时间复杂度

四. 数据结构

数据是一个抽象的概念,将其分类后得到程序设计语言中的基本类型。
数据元素之间不是独立的,存在特点的关系,这些关系便是数据结构。
程序=算法+数据结构
算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体。
抽象数据类型:指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起,进行封装。
常用的数据运算有五种:插入,删除,修改,查找和排序

标签:

未经允许不得转载:作者:756-周同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法(一)—– 算法效率》 发布于2020-06-11

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录