算法的时间复杂度和空间复杂度-创新互联

一、算法的时间复杂度

1.时间复杂度:指算法执行所需要的计算工作量

站在用户的角度思考问题,与客户深入沟通,找到贵阳网站设计与贵阳网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站建设、成都网站制作、企业官网、英文网站、手机端网站、网站推广、域名注册、网络空间、企业邮箱。业务覆盖贵阳地区。

2.时间频度:一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)), 称O(f(n)) 为算法的渐近时间复杂度,简称时间复杂度。

在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如 T(n)=n^2+3n+4与 T(n)=4n^2+2n+1它们的频度不同,但时间复杂度相同,都为O(n²)。在 T(n)=4n^2-2n+1中,就有f(n)=n²,使得T(n)/f(n)的极限值为4,那么O(f(n)),也就是时间复杂度为O(n²)。

  例如:T(n) = n+1 随着n的增大,1对结果的影响可以忽略不记,所以执行时间可以记作O(n)

3.常用函数阶

  一般取最坏情况作为算法复杂度的度量。

f(n)=1时,时间复杂度为O(1),可以称为常数阶。

  f(n)=n时,时间复杂度为O(n),可以称为线性阶。

  f(n)=logn时,时间复杂度为O(logn),可以称为对数阶。

  f(n)=nlogn时,时间复杂度为O(nlogn),可以称为nlogn阶。

  f(n)=n³时,时间复杂度为O(n³),可以称为立方阶。

  f(n)=2ⁿ时,时间复杂度为O(2ⁿ),可以称为指数阶。

  f(n)=n!时,时间复杂度为O(n!),可以称为阶乘阶。

  f(n)=√n时,时间复杂度为O(√n),可以称为平方根阶。

从图中可以看出:O(1)二、算法的空间复杂度

数据从输入到输出中间的处理过程是需要容器的,换句话说就是需要空间的。

1.空间复杂度:算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

2.空间类型

  • 输入空间:存储输入数据所需的空间大小;
  • 暂存空间: 算法运行过程中,存储所有中间变量和对象等数据所需的空间大小;
  • 输出空间: 算法运行返回时,存储输出数据所需的空间大小;
    通常情况下,空间复杂度指在输入数据大小为N时,算法运行所使用的暂存空间 + 输出空间的总体大小。

在这里插入图片描述

3.常见函数阶

根据从小到大排列,常见的算法空间复杂度有:
O(1)<O(logn)<O(n)<O(n^2)<O(2^n)

在这里插入图片描述

常数O(1):

普通常量、变量、对象、元素数量与输入数据大小N无关的集合,皆使用常数大小的空间。

def algorithm(N):
	num = 0
	nums = [0] * 10000
	node = Node(0)
	dic = {0: '0'}

如以下代码所示,虽然函数test()调用了N次,但每轮调用后test()已返回,无累计栈帧空间使用,因此空间复杂度仍为O(1)。

def algorithm(N)
	for _ in range(N):
		test()
线性O(N)

元素数量与N呈线性关系的任意类型集合(常见于一维数组、链表、哈希表等),皆使用线性大小的空间。

def algorithm(N):
	nums_1 = [0] * N
	nums_2 = [0] * (N // 2)

	nodes = [Node(i) for i in range(N)]
	
	dic = {}
	for i in range(N):
		dic[i] = str(i)

如下图与代码所示,此递归调用期间,会同时存在N个未返回的algorithm()函数,因此使用O(N)大小的栈帧空间。

def algorithm(N):
	if N<= 1: return 1
	return algorithm(N - 1) + 1

在这里插入图片描述

平方O(N2):

元素数量与N呈平方关系的任意类型集合(常见于矩阵),皆使用平方大小的空间。

def algorithm(N):
    num_matrix = [[0 for j in range(N)] for i in range(i)]
    node_matrix = [[Node(j) for j in range(N)] for i in range(N)]

如下图与代码所示,递归调用时同时存在 N 个未返回的algorithm()函数,使用 O(N) 栈帧空间;每层递归函数中声明了数组,平均长度为N/2 ,使用 O(N)空间;因此总体空间复杂度为 O(N2)。

def algorithm(N):
    if N<= 0: return 0
    nums = [0] * N      # O(N)
    return algorithm(N - 1)

在这里插入图片描述

指数O(2N) :

指数阶常见于二叉树、多叉树。例如,高度为N的满二叉树的节点数量为2N,占用O(2N)大小的空间;同理,高度为N的满m叉树的节点数量为mN,占用O(mN) = O(2N)大小的空间。

在这里插入图片描述

对数O(logN) :

对数阶常出现于分治算法的栈帧空间累计、数据类型转换等,例如:

  1. 快速排序 ,平均空间复杂度为 Θ(logN) ,最差空间复杂度为 O(N) 。拓展知识:通过应用 Tail Call Optimization ,可以将快速排序的最差空间复杂度限定至O(N) 。
  2. 数字转化为字符串 ,设某正整数为 N ,则字符串的空间复杂度为 O(logN) 。推导如下:正整数 N 的位数为 log10N ,即转化的字符串长度为log10N,因此空间复杂度为 O(logN) 。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前文章:算法的时间复杂度和空间复杂度-创新互联
网页URL:http://scyanting.com/article/dphseh.html