2020-11-14 数据结构与算法(1)

1411-李同学

发表文章数:148

热门标签

,
首页 » 数据结构 » 正文

数据结构与算法(Python)

引入

枚举法:如果a+b+c=1000,a2+b2=c**2, 如何求出所有的abc的可能。

import time

#笨蛋算法
start=time.time()
for a in range(1,1000):
    for b in range (1,1000):
        for c in range (1,1000):
            if a+b+c==1000 and a**2+b**2==c**2:
                print(a,b,c)
end=time.time()
print("time:{0}".format(end-start))
#换了一种方法,计算结果更快了
start=time.time()
for a in range(1,1000):
    for b in range (1,1000-a):
        c=1000-a-b
        if  a**2+b**2==c**2:
            print(a,b,c)
end=time.time()
print("time:{0}".format(end-start))
'''
result:
200 375 425
375 200 425
time:81.97971296310425
200 375 425
375 200 425
time:0.28323984146118164
可以观察到第二种的运算效率远高于第一种。限定了b的范围,减少了变量c的循环次数。
'''

算法的概念

算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输入设备或者某个存储地址供以后再调用

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

算法的五大特性

  • 输入:算法具有0个或多个输入

  • 输出:算法至少有一个或多个输出

  • 有穷性:算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成

  • 确定性:算法中的每一步都有确定的含义,不会出现二义性:看到这种思路就知道要做什么

  • 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完:可以应用到实际的程序当中。

第二次尝试

import time


#换了一种方法,计算结果更快了
start=time.time()
for a in range(0,1001):
    for b in range (0,1001-a):
        c=1000-a-b
        if  a**2+b**2==c**2:
            print(a,b,c)
end=time.time()
print("time:{0}".format(end-start))
'''
result:
0 500 500
200 375 425
375 200 425
500 0 500
time:0.31076955795288086
'''

算法效率衡量

执行时间反应算法效率

实现算法程序的执行时间可以反映出算法的效率,即算法的优劣

单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的。

时间复杂度与”大O计法“

每台机器执行的总时间不同,但是执行基本运算数量大体相同。

时间复杂度:描述时间上的效率问题, 经历了多少基本运算步骤。T(n)

  • 第一次尝试运算步骤:100010001000*2

    T(n)=N^3 * 2, N代表了问题的规模

    T(n)=N^ * k+c, 可以理解为两个T属于一个量级

渐近函数:g(n)=N^3, 可以理解为g函数时T函数的渐近函数。g(n)称为一个时间复杂度的大O计法。

最坏时间复杂度

同样的算法对于处理数据的不同也会复杂度也会不同。

  • 算法完成工作最少需要多少基本操作,即最优时间复杂度

  • 算法完成工作最多需要多少基本操作,即最坏时间复杂度

  • 算法完成工作平均需要多少基本操作,即平均时间复杂度。

主要关注最坏时间复杂度,是一种保证,表明算法在此种程度的基本操作中一定能完成工作。

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

  • 基本操作,即只有常数项,认为其时间复杂度未O(1)

  • 顺序结构,按加法计算

  • 循环结构:按乘法计算

  • 分支结构:时间复杂度取最大值

  • 判断一个算法效率时,往往只需要关注最高次项,,其他次项和常数项基本可以忽略。

我们所分析的算法的时间复杂度都是指最坏时间复杂度。

对于第二次改进的时间复杂度的分析 T(n)=n^2 *(1+max(0,1))=n2+2=O(n2)

常见的时间复杂度

2020-11-14 数据结构与算法(1)
2020-11-14 数据结构与算法(1)

Python 内置类型性能分析

列表添加

  • list.append()

  • list.insert()

timeit模块

用来测试一小段python代码的执行速度

class timeit.Timer(stmt=“pass”,setup=“pass”,timer=)

  • Timer 是测量小段代码执行速度的类

  • stmt参数时要测试的代码语句

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

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

time.Timer.timeit(number=1000000)

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

list测试操作

from timeit import Timer

def test1():
    list5=[]

    for i in range (10000):
        list5.append(i)

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

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


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

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

def test6():
    list10=[]
    for i in range(10000):
        list10.append(i)

def test7():
    list11=[]
    for i in range(10000):
        list11.insert(0,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 for i in range]:",timer3.timeit(1000))

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

timer5= Timer("test5()","from __main__ import test5")
print("extend:",timer5.timeit(1000))

timer6= Timer("test6()","from __main__ import test6")
print("append:",timer6.timeit(1000))

timer7= Timer("test7()","from __main__ import test7")
print("insert:",timer7.timeit(1000))

'''
result:
append: 0.4245253
+: 89.80185970000001
[i for i in range]: 0.20069589999999993
list(range(1000)): 0.10388779999999986
append: 0.4383290999999998
insert: 13.8358056
insert远不如append块,列表存储方式决定的。
'''

2020-11-14 数据结构与算法(1)
2020-11-14 数据结构与算法(1)

数据结构引入

数据结构指数据对象中数据元素之间的关系。数据结构就是对基本类型的封装

列表、元组、字典。需要自己去定义数据结构,不一样的数据结构的时间复杂度是不一样的。

==算法与数据结构的区别:

数据结构只是静态的描述了数据元素之间的关系

程序=数据结构+算法

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

抽象数据模型

抽象数据模型(ADT)的含义是指一个数学模型以及定义在次数学模型上的一组操作,即把数据类型和数据类型上的运算捆在一起,进行封装。
抽象数据模型=数据类型+数据类型支持的操作

常用的数据运算有五种:

  • 插入

  • 删除

  • 修改

  • 查找

  • 排序

#数据类型
[
    ("lixuan",24,"beijing"),
    ("lixuan",24,"beijing"),

]
#数据类型支持的操作
class student(object):
    def adds(self):
        pass
    def pop(self):
        pass
    def sort(self):
        pass
    def modify(self):
        pass
#数据类型+数据类型支持的操作即为抽象数据模型

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

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录