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

一、算法的时间复杂度

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),另外，在时间频度不相同时，时间复杂度有可能相同，如 与 它们的频度不同，但时间复杂度相同，都为O(n²)。在 中，就有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):

普通常量、变量、对象、元素数量与输入数据大小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元起，快前往官网查看详情吧

名称栏目：算法的时间复杂度和空间复杂度-创新互联
文章链接：http://cdiso.cn/article/dphseh.html