Python数据结构与算法之算法分析详解

目录
  • 0. 学习目标
  • 1. 算法的设计要求
    • 1.1 算法评价的标准
    • 1.2 算法选择的原则
  • 2. 算法效率分析
    • 2.1 大O表示法
    • 2.2 常见算法复杂度
    • 2.3 复杂度对比
  • 3. 算法的存储空间需求分析
  • 4. Python内置数据结构性能分析
    • 4.1 列表性能分析
    • 4.2 字典性能分析

0. 学习目标

我们已经知道算法是具有有限步骤的过程,其最终的目的是为了解决问题,而根据我们的经验,同一个问题的解决方法通常并非唯一。这就产生一个有趣的问题:如何对比用于解决同一问题的不同算法?为了以合理的方式提高程序效率,我们应该知道如何准确评估一个算法的性能。

通过本节学习,应掌握以下内容:

  • 了解算法分析的重要性
  • 能够熟练使用大O表示法分析算法的时间复杂度
  • 掌握空间复杂度分析方法
  • 了解 Python 列表和字典常见操作的时间复杂度

1. 算法的设计要求

算法分析的主要目标是从运行时间和内存空间消耗等方面比较算法。

1.1 算法评价的标准

一个好的算法首先应该是“正确”的,其对于每个输入实例均能终止并给出正确的结果,能够正确解决给定的计算问题。此外,还需要考虑以下方面:

  • 高效性:执行算法所需要的时间;
  • 低存储量:执行算法所耗费的存储空间,其中主要考虑辅助存储空间;
  • 可读性:算法应易于理解,易于编码,易于调试等等。

1.2 算法选择的原则

一个算法同时可以满足存储空间小、运行时间短、其它性能也好是很难做到的,很多情况下,我们不得不对性能进行取舍,在实际选择算法时,我们通常遵循以下原则:

  • 若该程序使用次数较少,则力求算法简明易懂;
  • 对于反复多次使用的程序,应尽可能选用快速的算法;
  • 若待解决的问题数据量极大,机器的存储空间较小,则相应算法主要考虑如何节省空间。

2. 算法效率分析

算法效率分析根据算法执行所需的时间进行分析和比较,这也称为算法的执行时间或运行时间。要衡量算法的执行时间,一个方法就是做基准分析,这是一种事后统计的方法,其使用绝对的时间单位来记录程序计算出结果所消耗的实际时间。在 Python 中,可以使用 time 模块的 time 函数记录程序的开始时间和结束时间,然后计算差值,就可以得到以秒为单位的算法执行时间。

以计算斐波那契数列第 n 项为例(斐波那契数列从第3项开始,每一项都等于前两项之和),在计算斐波那契数列第 n 项前后调用 time 函数,计算执行时间:

import time

def fibo(n):
    start = time.time()
    a, b = 1, 1
    if n > 2:
        for i in range(n-2):
            a, b = b, a + b
    end = time.time()
    running = end-start
    return b, running

for i in range(5):
    results = fibo(100000)
    print('It takes {:.8f} seconds to calculate the 10000th item of Fibonacci sequence'.format(results[1]))

代码执行结果如下:

It takes 0.08275080 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08277822 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08176851 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08178067 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08081150 seconds to calculate the 10000th item of Fibonacci sequence

但是这种方法计算的是执行算法的实际时间,有两个明显的缺陷:1) 必须先运行依据算法编制的程序;2) 依赖于特定的计算机、编译器与编程语言等软硬件环境,容易掩盖算法本身的优劣。因此,我们希望找到一个独立于程序或计算机的指标,以用来比较不同实现下的算法。

2.1 大O表示法

为了摆脱与计算机硬件、软件有关的因素,我们需要一种事前分析估算的方法。可以认为特定算法的“运行工作量”大小取决于问题的规模,或者说,它是问题规模的函数,这时我们就需要量化算法的操作或步骤。一个算法是由控制结构和基本操作构成的,因此可以将算法的执行时间描述成解决问题所需重复执行的基本操作数。需要注意的是,确定合适的基本操作取决于不同的算法。例如在计算斐波那契数列第 n 项时,赋值语句就是一个基本操作,而在计算矩阵乘法时,乘法运算则是其基本操作。

在上一节的 fibo 函数中,整个算法的执行时间与基本操作(赋值)重复执行的次数n 成正比,具体而言是 1 加上 n-2 个赋值语句,如果使用将其定义为函数可以表示为T(n)=n−1,其中 n为大于 2 的正整数。n常用于表示问题规模,我们可以使用问题规模 n的某个函数f(n) 表示算法中基本操作重复执行的次数,算法的时间量度可以表示如下:

T(n)=O(f(n))

随问题规模n的增大,T(n) 函数的某一部分会比其余部分增长得更快,算法间进行比较时这一起部分起决定性作用,T(n) 增长最快的部分也称为数量级函数。算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐近时间复杂度 (asymptotic time complexity),简称时间复杂度。数量级 (order of magnitude) 常被称作大O记法或大O表示法。

通过以上分析,我们可以将算法的渐近复杂度规则描述如下:

  • 如果运行时间是一个多项式的和,那么仅保留增长速度最快的项,去掉其他各项;
  • 如果剩下的项是个乘积,那么去掉所有常数。

假设某一算法的基本步骤数为T(n)=3n2+50n+2000,当 n nn 很小时 2000 对于函数的影响最大,但是随着n 的增长n2将逐渐变得更重要,以至于可以忽略其他两项以及n2的系数 3,因此可以说T(n) 的数量级是n2或写为O(n2)。

算法的性能有时不仅依赖问题的规模,还取决于算法的输入值,输入令算法运行最慢的情况称为最坏情况,输入令算法运行最快的情况称为最好情况,随机输入的情况下算法的性能介于两种极端情况之间,称为平均情况。

2.2 常见算法复杂度

下表列出了一些常见的大O表示法实例:

2.2.1 常数复杂度

常数复杂度表示,算法的渐进复杂度域输入的规模无关,例如求列表的长度等都属于常数复杂度。常数复杂度和代码中是否包含循环没有必然关系,例如循环打印 100 次 “Hello world”,这与输入规模并没有什么关系,因此其也是属于常数复杂度。

2.2.2 对数复杂度

对数复杂度表示函数的增长速度至少是输入规模的对数,当我们谈论对数复杂度时,我们并不关系对数的底数,这是由于可以使用换底公式,将原来底数的对数乘以一个常数转换为另一个底数:

其中,a aa 和 b bb 均为常数。例如以下代码,将一个正整数转换为字符串:

def int_to_str(num):
    digits = "0123456789"
    result = ''
    if num == 0:
        result = '0'
    else:
        while num > 0:
            result = digits[num % 10] + result
            num = num // 10
    return result

上述代码中只包括一个循环,且没有调用其它函数,因此我们只需找出循环迭代次数——在 num 为 0 之前所需的整数除法的次数log10n。因此函数 int_to_str 的复杂度是O(logn)。

2.2.3 线性复杂度

线性复杂度在列表中等序列数据类型总十分常见,因为算法通常需要遍历处理序列中的每一个元素。例如将列表中的每个元素加上常数 10:

def add_constant(list_o):
    for i in range(len(list_o)):
        list_o[i] += 10

这个函数的复杂度就与列表的长度成线性关系,也就是O(n)。

2.2.4 线性对数复杂度

线性对数复杂度是两项的乘积,每个项都依赖于输入的规模,例如将列表中每一项正整数转换为字符串。很多实用算法的复杂度都是对数线性的。

2.2.5 多项式复杂度

多项式复杂度的增长速度是输入规模的 k kk 次幂,其中最常见的是平方复杂度,例如求列表 list_a 和 list_b 的交集:

def intersect(list_a, list_b):
    # 第一部分
    temp = []
    for i in list_a:
        for j in list_b:
            if i == j:
                temp.append(i)
                break
    # 第二部分
    result = []
    for i in temp:
        if i not in result:
            result.append(i)
    return result

intersect 函数第一部分的复杂度显然是O(len(list_a))∗O(len(list_b)),第二部分代码用于去除第一部分得到结果列表中的重复元素,虽然其中仅包含一个循环语句,但是测试条件 if i not in result 需要检查 result 中的每个元素,因此第二部分的复杂度为O(len(temp))∗O(len(result)),tmp 和 result 的长度取决于 list_a 和 list_b 中长度较小的那个,根据渐进复杂度规则可以将其忽略。最终,intersect 函数的复杂度就是O(n2)。

2.2.6 指数复杂度

指数复杂度算法的解决时间随输入规模的指数增长。在以下示例中,由于 1 左移 num 位得到 end,因此 end 实际上等于2num,因此循环中计算了2num次加法,时间复杂度为O(2n)。

def calculate(num):
    result = 0
    end = 1 << num
    for i in range(end):
        result += i
    return result

2.3 复杂度对比

为了直观的观察到各种复杂度的增长情况,使用统计图来对比各种复杂度算法的运行时间增长速度。

从上图可以看出,对数复杂度随问题规模的增长,运行时间的增长很小,几乎和常数复杂度算法一样优秀,通常只有当输入规模很大时才能直观的看出两者之间的差别,而线性复杂度和对数复杂度的区别在输入规模很小时就非常明显了。

虽然O(logn) 的增长速度很慢,但是在线性乘法因子的加持下,其增长速率高于线性复杂度,但与平方复杂度的增长速度相比,就不值一提了,因此在实际情况下,具有O(nlogn) 复杂度的算法执行速度还是很快的。而指数复杂度除了对那些规模特别小的输入,其运行时间都是不现实的,即使立方复杂度和其相比都相形见绌。

3. 算法的存储空间需求分析

在以上内容中讨论的都是代码的时间复杂度。这是由于,与时间复杂度相比,要想感觉到空间复杂度 (space complexity) 的影响比较困难。对于用户来说,程序运行完成需要 1 分钟还是 10 分钟是明显能够感觉到的,但程序使用的内存是 1 兆字节还是 10 兆字节则无法直观觉察。这也就是时间复杂度通常比空间复杂度更受关注的原因。通常只有当运行程序所需的存储空间超过了计算机内存时,空间复杂度才会受到关注。

类似于算法的时间复杂度,空间复杂度作为算法所需存储空间的量度,可以表示为:

S(n)=O(f(n))

一个程序的执行除了需要存储空间来寄存本身所用指令、常数变量和输入数据外,也需要一些辅助空间用于存储数据处理的中间数据。若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间,否则应同时考虑输入本身所需空间。若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。

4. Python内置数据结构性能分析

由于在之后的学习中,我们需要经常使用列表和字典作为构建其他数据结构的基石,因此了解这些数据结构操作的时间复杂度是必要的。

4.1 列表性能分析

Python 列表常见操作的时间复杂度如下表所示:

在列表中虽然 append() 操作和 insert() 操作都是向列表中添加一个元素,不同的是 append() 向列表末尾追加一个元素,而 insert() 在指定位置处插入元素,其后的元素都要向后移一位,因此它们的时间复杂度也不相同。

为了获取执行时间,这里使用 timeit 模块,该模块能够在一致的环境中执行函数。要使用 timeit 模块,首先需要创建一个 Timer 对象,其接受两个参数:第 1 个参数是要为之计时的 Python 语句;第 2 个参数是建立测试的 Python 语句。timeit 模块会统计多次执行语句要用多久,默认情况下,timeit 会执行 100 万次语句,并在完成后返回一个浮点数格式的秒数,可以给 timeit 传入参数 number,以指定语句的执行次数。

import timeit
import random
append_timeit = timeit.Timer('x.append(1)', 'from __main__ import x')
insert_timeit = timeit.Timer('x.insert(0, 1)', 'from __main__ import x')
for i in range(10000, 2000000, 20000):
    x = list(range(i))
    # 测试函数运行 1000 次所花的时间
    append_time = append_timeit.timeit(number=1000)
    x = list(range(i))
    # 测试函数运行 1000 次所花的时间
    insert_time = insert_timeit.timeit(number=1000)
    print("{}, {}, {}".format(i, append_time, insert_time))

在上例中,计时的语句是对 append 和 insert 操作的调用。建立测试的语句是初始化代码或构建环境导入语句,是执行代码的准备工作,示例中的 from __main__ import x 将 x 从 __main__ 命名空间导入到 timeit 设置计时的命名空间,用于在测试中使用列表对象 x,这么是为了在一个干净的环境中运行计时测试,以免某些变量以某种意外的方式干扰函数的性能。

从上图中可以看出,列表越长,insert 操作的耗时也随之变长,而 append 操作的耗时很稳定,符合O(n)和O(1) 的特征。

4.2 字典性能分析

Python 字典常见操作的时间复杂度如下表所示:

对比两表可以发现,即使是同一操作使用不同数据结构其复杂度也是不同的,例如包含操作 in。为了验证它们之间的不同,编写以下程序进行实验:

import timeit
import random
for i in range(10000, 1000000, 20000):
    t = timeit.Timer('random.randrange({}) in x'.format(i), 'from __main__ import random, x')
    x = list(range(i))
    list_time = t.timeit(number=1000)
    x = {j: j for j in range(i)}
    dict_time = t.timeit(number=1000)
    print("{}, {}, {}".format(i, list_time, dict_time))

从上图可以看出,随着规模的增长,对于字典而言,包含操作的耗时始终是基本恒定的,而对于列表而言,其包含操作的耗时呈线性增长。 

以上就是Python数据结构与算法之算法分析详解的详细内容,更多关于Python算法分析的资料请关注我们其它相关文章!

(0)

相关推荐

  • Python算法的时间复杂度和空间复杂度(实例解析)

    算法复杂度分为时间复杂度和空间复杂度. 其作用: 时间复杂度是指执行算法所需要的计算工作量: 而空间复杂度是指执行这个算法所需要的内存空间. (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度). 简单来说,时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间 计算时间复杂度的方法: 用常数1代替运行时间中的所有加法常数 修改后的运行次数函数中,只保留最高阶项 去除最高阶项的系数 时间复杂度 算法的

  • python数据结构算法分析

    目录 1.算法分析的定义 2. 大O记法 3. 不同算法的大O记法 3.1 清点法 3.2 排序法 3.3 蛮力法 3.4 计数法 4. 列表和字典操作的复杂度 4.1 列表 4.2 字典 前文学习: python数据类型: python数据结构:数据类型. python的输入输出: python数据结构输入输出及控制和异常. python面向对象: python数据结构面向对象. 今天我们来学习的内容是面试题中都避免不小了的问题,就是算法分析了,什么是算法分析,算法分析是用来分析一个算法的好坏

  • Python字典和列表性能之间的比较

    Python列表和字典 前面我们了解了 "大O表示法" 以及对不同的算法的评估,下面来讨论下 Python 两种内置数据类型有关的各种操作的大O数量级:列表 list 和字典dict. 这是 Python 中两种非常重要的数据类型,后面会用来实现各种数据结构,通过运行试验来估计其各种操作运行时间数量级. 对比 list 和 dict 操作如下: List列表数据类型常用操作性能: 最常用的是:按索引取值和赋值(v=a[i],a[i]=v),由于列表的随机访问特性,这两个操作执行时间与列

  • Python算法中的时间复杂度问题

    在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度.顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量算法占用的内存空间. 本文将从时间复杂度的概念出发,结合实际代码示例分析算法的时间复杂度. 渐进时间复杂度 时间复杂度是算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个算运行时间是比较困难的,所以通常关注的是时间频度,即算法运行计算操作的次数,记为T(n),其中n称为问题的规模. 同样,因为n是一个变量,n发生变化时

  • Python数据结构与算法之算法分析详解

    目录 0. 学习目标 1. 算法的设计要求 1.1 算法评价的标准 1.2 算法选择的原则 2. 算法效率分析 2.1 大O表示法 2.2 常见算法复杂度 2.3 复杂度对比 3. 算法的存储空间需求分析 4. Python内置数据结构性能分析 4.1 列表性能分析 4.2 字典性能分析 0. 学习目标 我们已经知道算法是具有有限步骤的过程,其最终的目的是为了解决问题,而根据我们的经验,同一个问题的解决方法通常并非唯一.这就产生一个有趣的问题:如何对比用于解决同一问题的不同算法?为了以合理的方式

  • python 换位密码算法的实例详解

     python 换位密码算法的实例详解 一前言: 换位密码基本原理:先把明文按照固定长度进行分组,然后对每一组的字符进行换位操作,从而实现加密.例如,字符串"Error should never pass silently",使用秘钥1432进行加密时,首先将字符串分成若干长度为4的分组,然后对每个分组的字符进行换位,第1个和第3个字符位置不变,把第2个字符和第4个字符交换位置,得到"Eorrrs shluoden v repssa liseltny" 二 代码:

  • python实现爬山算法的思路详解

    问题 找图中函数在区间[5,8]的最大值 重点思路 爬山算法会收敛到局部最优,解决办法是初始值在定义域上随机取乱数100次,总不可能100次都那么倒霉. 实现 import numpy as np import matplotlib.pyplot as plt import math # 搜索步长 DELTA = 0.01 # 定义域x从5到8闭区间 BOUND = [5,8] # 随机取乱数100次 GENERATION = 100 def F(x): return math.sin(x*x)

  • Python数据结构之列表与元组详解

    目录 Python 列表(list): 1.序列介绍: 2.列表的概述: 3.创建一个列表 4.列表的索引 5.列表的分片 6.列表的分片赋值 7.循环遍历列表 8.查找元素与计数 9.列表增加元素: 10.列表删除元素: 11.列表排序 Python 元组(tuple): 1.为什么要将元组设计成为不可变序列 2.创建元组 3.元组的遍历 4.元组的内置函数 Python 列表(list): 1.序列介绍:   序列是Python中最基本的数据结构.序列中的每个元素都分配一个数字 - 它的位置

  • C语言 数据结构与算法之字符串详解

    目录 串的定义 串的比较 串的抽象数据类型 串的初始化 相关定义初始化 定长类初始化 串的堆式顺序存储结构(Heap) 初始化堆字符串 赋值操作 比较两个堆字符串的大小 串的定义 零个或多个字符组成的有限序列 串的比较 串的比较实际上是在比较串中字符的编码 存在某个k < min(n,m),使得ai = bi (i = 1,2,3,4..k) 如果 ak < bk  -->  那么srt1 < srt2 (反之也成立) 除去相等的字符,在第一个不相等的字符位置以Ascii码进行比较

  • Python 数据结构之树的概念详解

    数据结构树简介 一.树简介 树(Tree)是一种抽象的数据结构,是一个数据的集合,集合中的数据组成了一个树状结构.例如上图,看起来像一棵倒挂的树,根朝上叶朝下. 树是由n(n>=0)个节点组成的具有层次关系的数据集合.当 n=0 时,树中没有节点,称为空树.当 n>0 时,有且仅有一个节点被称为根节点(Root),如果 n=1 ,树只有根节点一个节点.如果 n>1 ,除根节点外,将其余的节点分成m(m>0)个互不相交的数据集合,这 m 个集合每一个都要满足树的结构(有且仅有一个根节

  • Python实现的数据结构与算法之队列详解

    本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队

  • Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

随机推荐