Python数据结构与算法_第1节_引入概念

1389-李同学

发表文章数:35

首页 » 数据结构 » 正文

引入

  • 注意:命名时,py文件名最好为数字_英文,为了防止文件名与package名字重合。

第一次尝试

  • 如果 a+b+c=1000,且

    a

    2

    +

    b

    2

    =

    c

    2

    a^2 + b^2=c^2

    a2+b2=c2(a,b,c 为自然数),如何求出所有a、b、c可能的组合?

    • 看到这道题,如果不用math的方法,第一个反应就是把他们全部列出来,试一遍 —- 枚举法
# 枚举法来解决解方程式的问题:三重循环
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a**2 + b**2 == c**2 and a+b+c == 1000:
                print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

算法的提出

  • 算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。
  • 算法是独立存在的一种解决问题的方法和思想
  • 裘宗燕 《数据结构与算法 Python语言描述》
  • 《算法导论》
  • 《数据结构预算法 C语言描述》要比Python的深一些

算法的五大特性

  • 输入: 算法具有0个或多个输入
  • 输出: 算法至少有1个或多个输出
  • 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
  • **确定性:**算法中的每一步都有确定的含义,不会让其他人不理解,出现二义性
  • **可行性:**算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

第二次尝试

  • 刚刚的算法效率太低,我们可以根据a、b、c之间的关系来精简代码。
# 枚举法来解决解方程式的问题:两重循环
for a in range(0, 1001):
    for b in range(0, 1001-a):	# 因为b和c不会占用已选择出来的、a的数值
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print("a, b, c: %d, %d, %d" % (a, b, c))

算法效率衡量

执行时间反应算法效率

  • 实现算法程序的执行时间可以反应出算法的效率,即算法的优劣。
  • 但是单纯靠运行时间来比较算法的优劣并不一定是客观准确的!因为计算机的环境不同。

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

  • 每台计算机执行的总时间不同,但是执行基本运算数量大体相同。
  • 时间复杂度:程序运行时候,基本的运算数量
    • 第一次尝试中:
      • T(时间复杂度) =

        1000

        1000

        1000

        2

        1000 * 1000 *1000* 2

        1000100010002,跟问题的规模有关系

      • 假设

        a

        +

        b

        +

        c

        =

        n

        a+b+c=n

        a+b+c=n

        T

        (

        n

        )

        =

        n

        3

        +

        2

        T(n) = n^3 +2

        T(n)=n3+2

如何理解“大O记法”

  • 更关心数量级,不那么关心系数。
  • T

    (

    n

    )

    =

    n

    3

    2

    T(n) = n^3 *2

    T(n)=n32

    T

    (

    n

    )

    =

    n

    3

    2

    T(n) = n^3 *2

    T(n)=n32 在同一个数量级,图像走向也一样。都为

    g

    (

    n

    )

    =

    n

    3

    g(n) = n^3

    g(n)=n3级。

    g

    (

    n

    )

    g(n)

    g(n)就是

    T

    (

    n

    )

    T(n)

    T(n)的渐进函数(忽略函数),记为

    f

    (

    n

    )

    =

    O

    (

    g

    (

    n

    )

    )

    f(n) = O(g(n))

    f(n)=O(g(n))

最坏时间复杂度

  • 数据的情况不同,数据处理所需要的步骤也不同。
  • 算法完成工作最少需要多少基本操作,即最优时间复杂度,参考价值不高。
  • 算法完成工作最多需要多少基本操作,即最坏时间复杂度,一般考虑的也是他。
  • 算法完成工作平均需要多少基本操作,即平均时间复杂度,关注度最小。

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

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

算法分析

  • 第一次尝试:

    O

    (

    n

    3

    )

    O(n^3)

    O(n3)

  • 第二次尝试:

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)

常见时间复杂度

执行次数函数举例 非正式术语
12 O(1) 常数阶

2

n

+

3

2^n+3

2n+3

O(n) 线性阶

3

n

2

+

2

n

+

1

3n^2+2n+1

3n2+2n+1

O

(

n

2

)

O(n^2)

O(n2)

平方阶

5

l

o

g

2

n

+

20

5log_2n+20

5log2n+20

O

(

l

o

g

(

n

)

)

O(log(n))

O(log(n))

对数阶

2

n

+

3

n

l

o

g

2

n

+

19

2n+3nlog_2n+19

2n+3nlog2n+19

O

(

n

l

o

g

(

n

)

)

O(nlog(n))

O(nlog(n))

nlogn阶

6

n

3

+

2

n

2

+

3

n

+

4

6n^3+2n^2+3n+4

6n3+2n2+3n+4

O

(

n

3

)

O(n^3)

O(n3)

立方阶

2

n

2^n

2n

O(2^n) 指数阶

常见时间复杂度之间的关系

  • 根据图像的关系判断时间复杂度的判断
  • O

    (

    1

    )

    <

    O

    (

    l

    o

    g

    n

    )

    <

    O

    (

    n

    )

    <

    O

    (

    n

    l

    o

    g

    n

    )

    <

    O

    (

    n

    2

    )

    <

    O

    (

    n

    3

    )

    <

    O

    (

    2

    n

    )

    <

    O

    (

    n

    !

    )

    <

    O

    (

    n

    n

    )

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

    O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

Python内置类型性能分析

  • 时间复杂度为O(1)的是基本操作行,不是函数。
  • 比如list.append()这个函数的时间复杂度不是1。可以有timeit模块来判断。

timeit模块

  • timeit模块可以用来测试一小段Python代码的执行速度。
  • class timeit.Timer(stmt=‘pass’, setup=‘pass’, timer=)
    • Timer是测量小段代码执行速度的类。
    • stmt参数是要测试的代码语句(statment);
    • setup参数是运行代码时需要的设置;
    • timer参数是一个定时器函数,与平台有关。
  • timeit.Timer.timeit(number=1000000)
    • Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数,默认为1000000次。方法返回执行代码的平均耗时,一个float类型的秒数。
# 用timeit模块测试创建list的一个操作的效率
from timeit import Timer
def test1():
	l = []
	for i in range(1000):
		l.append(i)
t1 = Timer("test1()", "from __main__ import test1")	# setup是设置环境,在当前文件内调用内部文件,文件名为__main__
print("append", t1.timeit(number = 1000), "seconds.")
# 在append列表的时候,extend和 +=更快一点,不要使用+。

list内置操作的时间复杂度

Python数据结构与算法_第1节_引入概念

dict内置操作的时间复杂度

Python数据结构与算法_第1节_引入概念

数据结构

  • 我们希望算法解决问题的效率越快越好,于是我们就需要考虑数据究竟如何保存的问题,这就是数据结构。

概念

  • 序列已经是Python封装的一种高级结构了。数据结构就是对基本数据类型的一次封装,把他们组合在一起。

算法与数据结构的区别

  • 数据结构只是静态的描述了数据元素之间的关系。
  • 高效的程序需要在数据结构的基础上设计和选择算法。
  • 程序 = 数据结构 + 算法

抽象数据类型(Abstract Data Type)

  • 抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起,进行封装。
  • 最常用的数据运算有五种:
    • 插入
    • 删除
    • 修改
    • 查找
    • 排序

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

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录