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

算法复杂度分为时间复杂度和空间复杂度。

其作用：

时间复杂度是指执行算法所需要的计算工作量；
而空间复杂度是指执行这个算法所需要的内存空间。
（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

简单来说，时间复杂度指的是语句执行次数，空间复杂度指的是算法所占的存储空间

计算时间复杂度的方法：

  • 用常数1代替运行时间中的所有加法常数
  • 修改后的运行次数函数中，只保留最高阶项
  • 去除最高阶项的系数

时间复杂度

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间，时间复杂度常用“O”表述，使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况

时间复杂度是用来估计算法运行时间的一个式子（单位），一般来说，时间复杂度高的算法比复杂度低的算法慢

print('Hello world') # O(1)
# O(1)
print('Hello World')
print('Hello Python')
print('Hello Algorithm')
for i in range(n): # O(n)
 print('Hello world')
for i in range(n): # O(n^2)
 for j in range(n):
 print('Hello world')
for i in range(n): # O(n^2)
 print('Hello World')
 for j in range(n):
 print('Hello World')
for i in range(n): # O(n^2)
 for j in range(i):
 print('Hello World')
for i in range(n):
 for j in range(n):
 for k in range(n):
  print('Hello World') # O(n^3)

几次循环就是n的几次方的时间复杂度

n = 64
while n > 1:
 print(n)
 n = n // 2

26 = 64，log264 = 6，所以循环减半的时间复杂度为O(log2n)，即O(logn)

如果是循环减半的过程，时间复杂度为O(logn)或O(log2n)

常见的时间复杂度高低排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

空间复杂度

空间复杂度：用来评估算法内存占用大小的一个式子

a = 'Python' # 空间复杂度为1
# 空间复杂度为1
a = 'Python'
b = 'PHP'
c = 'Java'
num = [1, 2, 3, 4, 5] # 空间复杂度为5
num = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] # 空间复杂度为5*4
num = [[[1, 2], [1, 2]], [[1, 2], [1, 2]] , [[1, 2], [1, 2]]] # 空间复杂度为3*2*2

定义一个或多个变量，空间复杂度都是为1，列表的空间复杂度为列表的长度

总结

以上所述是小编给大家介绍的Python算法的时间复杂度和空间复杂度，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

赞 (0)

相关推荐

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

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

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

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

  • python算法与数据结构之冒泡排序实例详解

    一.冒泡排序介绍 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 二.冒泡排序原理 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这一步做完,最后的元素应该会是最大的数. 针对所有的

  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    C语言 超详细讲解算法的时间复杂度和空间复杂度

    目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit

  • C语言算法的时间复杂度和空间复杂度

    C语言算法的时间复杂度和空间复杂度

    目录 1.算法效率 1.1 如何衡量一个算法的好坏 1.2算法的复杂度 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3常见时间复杂度计算举例 3.空间复杂度 4.常见复杂度对比 5.复杂度的OJ练习 5.1消失的数字OJ 3.2 旋转数组OJ 1.算法效率 1.1 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: long long Fib(int N) { if (N < 3) return 1; return Fib(N - 1) +

  • python算法学习之计数排序实例

    python算法学习之计数排序实例 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, B, k):    """计数排序,伪码如下:    COUNTING-SORT(A, B, k)    1  for i ← 0 to k // 初始化存储区的值    2    do C[i] ← 0    3  for j ← 1 to length[A] // 为各值计数    4    do C[A[j]] ← C[A

  • Python建立Map写Excel表实例解析

    Python建立Map写Excel表实例解析

    本文主要研究的是用Python语言建立Map写Excel表的相关代码,具体如下. 前言:我们已经能够很熟练的写Excel表相关的脚本了.大致的操作就是,从数据库中取数据,建立Excel模板,然后根据模板建立一个新的Excel表,把数据库中的数据写入.最后发送邮件.之前的一篇记录博客,写的很标准了.这里我们说点遇到的新问题. 我们之前写类似脚本的时候,有个问题没有考虑过,为什么要建立模板然后再写入数据呢?诶-其实也不算是没考虑过,只是懒没有深究罢了.只求快点完成任务... 这里对这个问题进行思考阐

  • Python多线程threading和multiprocessing模块实例解析

    Python多线程threading和multiprocessing模块实例解析

    本文研究的主要是Python多线程threading和multiprocessing模块的相关内容,具体介绍如下. 线程是一个进程的实体,是由表示程序运行状态的寄存器(如程序计数器.栈指针)以及堆栈组成,它是比进程更小的单位. 线程是程序中的一个执行流.一个执行流是由CPU运行程序代码并操作程序的数据所形成的.因此,线程被认为是以CPU为主体的行为. 线程不包含进程地址空间中的代码和数据,线程是计算过程在某一时刻的状态.所以,系统在产生一个线程或各个线程之间切换时,负担要比进程小得多. 线程是一

  • python使用json序列化datetime类型实例解析

    使用python的json模块序列化时间或者其他不支持的类型时会抛异常,例如下面的代码: # -*- coding: cp936 -*- from datetime import datetime import json if __name__=='__main__': now = datetime.now() json.dumps({'now':now}) 运行会出现下面的错误信息: Traceback (most recent call last): File "C:\Users\xx\De

  • python删除过期log文件操作实例解析

    本文研究的主要是python删除过期log文件的相关内容,具体介绍如下. 1. 用Python遍历目录 os.walk方法可以很方便的得到目录下的所有文件,会返回一个三元的tupple(dirpath, dirnames, filenames),其中,dirpath是代表目录的路径,dirnames是一个list,包含了dirpath下的所有子目录的名字,filenames是一个list,包含了非目录的文件,如果需要得到全路径,需要使用os.path.join(dirpath,name).例如t

  • python中set()函数简介及实例解析

    set函数也是python内置函数的其中一个,属于比较基础的函数.其具体介绍和使用方法,下面进行介绍. set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集.差集.并集等. set,接收一个list作为参数 list1=[1,2,3,4] s=set(list1) print(s) #逐个遍历 for i in s: print(i) 输出: set([1, 2, 3, 4]) 1 2 3 4 使用add(key)往集合中添加元素,重复的元素自动过滤 list1

随机推荐