专栏首页python语言学习数据结构与算法初识

数据结构与算法初识

什么是计算机科学?

首先明确的一点就是计算机科学不仅仅是对计算机的研究,虽然计算机在科学发展的过程中发挥了重大的作用,

但是它只是一个工具,一个没有灵魂的工具而已。所谓的计算机科学实际上是对问题、解决问题以及解决问题的

过程中产生产生的解决方案的研究。例如给定一个问题,计算机科学家的目标是开发一个算法来处理该问题,

最终得到该问题的解、或者最优解。所以说计算机科学也可以被认为是对算法的研究。因此我们也可以感受到,

所谓的算法就是对问题进行处理且求解的一种实现思路或者思想。

如何形象化的理解算法与算法的意义

理解

一个常胜将军在作战之前都会进行战略的制定,目的是为了能够在最短的时间切成本消耗最低的情况下获取最终的胜利。 如果将编码作为战场,则程序员就是这场战役的指挥官,你如何可以将你的程序可以在最短且消耗资源最小的情况下获取 最终的执行结果呢?算法就是我们的策略!

意义

数据结构和算法思想的通用性异常的强大,在任何语言中都被使用,它们将会是我们编码生涯中伴随我们最长久利器(左膀右臂)。 有一定经验的程序员最终拼的就是算法和数据结构。数据结构和算法思想也可以帮助我们拓展和历练编码的思维,可以让我们更好的融入到编程世界的角角落落。

什么是算法分析?

刚接触编程的学生经常会将自己编写的程序和别人的程序做比对,获取在比对的过程中会发现双方编写的程序很相似但又各不相同。 那么就会出现一个有趣的现象:两组程序都是用来解决同一个问题的,但是两组程序看起来又各不相同,那么哪一组程序更好呢?

a+b+c=1000, a^2+b^2=c^2a, b, c 均为自然数),求出 a, b, c 可能的组合?

# 第一组代码
import datetime

starttime = datetime.datetime.now()

for a in range(0,1001): 
    for b in range(0,1001):
        for c in range(0,1001):
            if a+b+c == 1000 and a**2+b**2 == c**2:
                print(a,b,c)

endtime = datetime.datetime.now()
print (endtime - starttime)

# 运行结果 这组代码运行4分多种才求出结果
0 500 500
200 375 425
375 200 425
500 0 500
0:04:15.526003
# 第二组代码
import datetime

starttime = datetime.datetime.now()

for a in range(0,1001):
    for b in range(0,1001):
        c = 1000-a-b
        if a+b+c == 1000 and a**2+b**2 == c**2:
                print(a,b,c)
                
endtime = datetime.datetime.now()
print (endtime - starttime)

# 运行结果  这组代码运行2秒左右就求出结果,明显优于上组代码
0 500 500
200 375 425
375 200 425
500 0 500
0:00:02.117703

评判程序优劣的方法

  • 消耗计算机资源和执行效率(无法直观看到程序运行占用的资源,执行效率受计算机硬件影响)
  • 计算算法执行的耗时(不推荐,因为会受计算机硬件和执行环境的影响,要用程序的平均耗时来对比)
  • 时间复杂度(推荐)

时间复杂度 大 \mathcal{O} 表达公式 T(n)=\mathcal{O}(f(n))

  • 评判规则:量化算法执行的操作/执行步骤的数量
  • 最重要的项:时间复杂度表达式中最有意义的项
  • 使用大 \mathcal{O} 记法来表示时间复杂度
    • \mathcal{O}(n) (最重要的项,最有意义的项)
    • 不考虑常数项 2n\Rightarrow n
    • 不考虑低次项 n^2+n\Rightarrow n^2
    • 一般时间复杂度都是讲“最差”的情况
  • 时间复杂度越低算法越优
  • 常见的时间复杂度:
    • \mathcal{O}(1) < \mathcal{O}(logn) < \mathcal{O}(n) < \mathcal{O}(nlogn) < \mathcal{O}(n^2) < \mathcal{O}(n^3) < \mathcal{O}(2^n) < \mathcal{O}(n!) < \mathcal{O}(n^n)
# 时间复杂度
def sumOfN(n):
    theSum = 0              # 1
    for i in range(1,n+1):  # n+1
        theSum = theSum + i
    return theSum
print(sumOfN(10))
# 1+n+1 ==> O(n)

a=5                    # 1
b=6                    # 1 
c=10                   # 1
for i in range(n):    
   for j in range(n):  # 3n**2  
      x = i * i
      y = j * j
      z = i * j
for k in range(n):     # 2n
   w = a*k + 45
   v = b*b
d = 33                 # 1

# 3+3n**2+2n+1 ==>n**2==>O(n**2)

数据结构

  • 概念:对于数据(基本类型的数据(int,float,char))的组织方式就被称作为数据结构。 数据结构解决的就是一组数据如何进行保存,保存形式是怎样的。(python语言中基本数据类型都是对象)
  • 案例: 需要存储一些学生的学生信息(name,score),那么这些数据应该如何组织呢?查询某一个具体学生的时间复杂度是什么呢?(三种组织方式)
# 第一种 时间复杂度 O(n)
[{
    'name':'xxx',
    'score':'xxx'
},{
    'name':'xxx',
    'score':'xxx'
},{
    'name':'xxx',
    'score':'xxx'
}]
# 第二种 时间复杂度 O(n)
[
    ('name','score'),
    ('name','score'),
    ('name','score')
]
# 第三种 时间复杂度 O(1)
{
    'zhangsan':{'score':'xxx'},
    'lisi':{'score':'xxx'}
}

数据结构与算法的关系?

使用不同的形式组织数据,在基于查询时的时间复杂度是不一样的。因此认为算法是为了解决实际问题而设计的,

数据结构是算法需要处理问题的载体。

python数据结构性能如分析

在列表的操作有一个非常常见的编程任务就是是增加一个列表。我们马上想到的有两种方法可以创建更长的列表,

可以使用 append 方法或拼接运算符。但是这两种方法那种效率更高呢。这对你来说很重要,因为它可以帮助你通过

选择合适的工具来提高你自己的程序的效率。

  • timeit模块:该模块可以用来测试一段python代码的执行速度/时长。
  • Timer类:该类是timeit模块中专门用于测量python代码的执行速度/时长的。原型为:
class timeit.Timer(stmt='pass',setup='pass')
  • stmt参数:表示即将进行测试的代码块语句。
  • setup:运行代码块语句时所需要的设置。
  • timeit函数:
timeit.Timer.timeit(number=100000) # 该函数返回代码块语句执行number次的平均耗时。
  • 实例化一个空列表,然后将 0\sim n 范围的数据添加到列表中。(四种方式)
from timeit import Timer
def test01():
    alist = []
    for i in range(1000):
        alist += [i]
    return alist
def test02():
    alist = []
    for i in range(1000):
        alist.append(i)
    return alist
def test03():
    return [i for i in range(1000)]
def test04():
    alist = list(range(1000))
    return alist
if __name__ == '__main__':
    timer = Timer('test01()','from __main__ import test01')
    t1 = timer.timeit(100000)
    print(t1)
    
    timer2 = Timer('test02()','from __main__ import test02')
    t2 = timer.timeit(100000)
    print(t2)
    
    timer3 = Timer('test03()','from __main__ import test03')
    t3 = timer.timeit(100000)
    print(t3)
    
    timer4 = Timer('test04()','from __main__ import test04')
    t4 = timer.timeit(100000)
    print(t4)
# 执行结果 第四种方式时间最短 list(range(1000))
11.752772499999992
10.816332999999986
11.822587399999975
9.485878500000013

作 者:郭楷丰

出 处:https://www.cnblogs.com/guokaifeng/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Selenium浏览器自动化测试工具

    出 处:https://www.cnblogs.com/guokaifeng/

    郭楷丰
  • python 合集set,交集,并集,差集,对称差集别搞混

    郭楷丰
  • 初识数据库管理系统

    郭楷丰
  • 盘点人工智能十大经典应用领域、图解技术原理

    导读:本文通过案例分门别类地深入探讨人工智能的实际应用。案例甚多,此处所列举的仅是九牛一毛。本该按行业或业务对这些案例进行分类,但相反我选择按在行业或业务中最可...

    华章科技
  • 算法中的时间复杂度

    程序员写代码过程中总要用到算法,而不同的算法有不同的效率,时间复杂度是用来评估的算法的效率的一种方式。

    zhangyunfeiVir
  • 基于时空网络的出租车OD需求预测-模型框架(附数据集下载方式)

    《Contextualized Spatial–Temporal Network for Taxi rigin-Destination Demand Predi...

    深度学习与交通大数据
  • 数据结构与算法 1-3 最坏时间复杂度与计算规则

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍算法时间复杂度的三种不同程度:最坏时间复杂度、最优时间复杂度以及平均时间复杂度,并且介绍...

    触摸壹缕阳光
  • 腾讯云服务器自助更换IP教程(无需任何费用)

    1.我们需要先将IP转换为弹性公网IP,点击如下位置即可(转换为弹性公网IP后才能对IP进行解绑更换等操作)

    古人诗
  • 图解TCP/IP(一)

      IP(Internet Protocol) IP/ICMP -数据链路层的主要作用是在互连同一种数据链路的节点之间进行包传递。而一旦跨越多种数据链路,就需要...

    互联网金融打杂
  • hdu 1069 Monkey and Banana 经典dp

    题意:给n个 维度为(x,y,z)的 立方体,垒起来,要求下层长宽严格大于上层,求最大高度

    用户2965768

扫码关注云+社区

领取腾讯云代金券