1、算法复杂度
算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间的大小。
2、时间复杂度
1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:
T(n)=O(f(n))
分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。
2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))
例:算法:
for(i=1;i<=n;++i) {
for(j=1;j<=n;++j) {
c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n的平方 次
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n的三次方 次
}
}
}
则有 T(n)= n的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级 则有f(n)= n的三次方,然后根据T(n)/f(n)求极限可得到常数c 则该算法的 时间复杂度:T(n)=O(n的三次方)
3.分类
按数量级递增排列,常见的时间复杂度有: 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
3、空间复杂度
一般是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占用的存储空间以及算法执行过程中所需要的额外空间。一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
(1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
(2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。
S(n)=O(f(n))
其中n为问题的规模,S(n)表示空间复杂度。
4、说明例子
时间复杂度描述一个算法对数据规模和执行时间之间的关系。
一个算法,处理n条数据需要的时间可以用表达式:a*n+b来表示的话,称它的时间复杂度为O(n),也就是说,100条数据需要1秒的话,1000条数据需要10s。如果是用表达式:a*n*n+b*n+c的话,复杂度为O(n的平方),这样100条1秒,1000条就要100s了。0(0)表达式为a*(n的0次方)+b,也就是个常数。这样无论100还是1000条都只需1秒。
空间复杂度类似,只是描述的是规模与存储空间的关系。下面来看个O(n)和O(1)的例子:
要从0加到n,我们会这么写:
int sum = 0;
for(int i = 0; i<=n; ++i)
{
sum += i;
}
一共算了n次加法,那么就说这个时间复杂度是O(n)。当然O(n)的精确的概念是,是n的最高次方,比如,某个计算共计算了3n + 2次,那么这个时间复杂度也是O(n),因为3n + 2中的最高次方是n。分析如下代码:
int sum = 0;
for(int i = 0; i<=n; ++i)
{
for(int j = 0; j <=n; ++j)
{
sum += (i + j);
}
}
很显然一共算了n^2次加法,那么就说这个时间复杂度是O(n^2),和上面类似,如果某个算法计算了3*n^2 + n + 1次,其时间复杂度仍然是O(n^2),因为3*n^2 + n + 1中最高的次方是n^2
所谓O(1)就是计算的次数是个常量,我们还以上面从0加到n的例子来说,如果我们用等差数列的公式,那么,代码可以这么写:
int sum = n * (n + 1) / 2
不管n有多大(当然不能溢出了),通过上面的公式只需计算一次,也就说计算的次数是不变的,这种情况的时间复杂度就可以说成O(1)。 再比如如果某个计算,不管其他条件怎么变化,均只需计算5次即可得出结果,那么这种情况的时间复杂度,也是O(1)。
5、复杂度判定
要在 hash 表中找到一个元素就是 O(1)
要在无序数组中找到一个元素就是 O(n)
访问数组的第 n 个元素是 O(1)
访问链表的第 n 个元素是 O(n)
简单的判断方法:
如果实现中没有循环就是 O(1)
如果实现中有一个循环就是 O(n)
注:f(n)相当于一个基本的计算单元如:f(n)=ax+2,它是一个线性函数。基于线性函数才能计算时间复杂度。
分享到:
相关推荐
简单来说,时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间 计算时间复杂度的方法: 用常数1代替运行时间中的所有加法常数 修改后的运行次数函数中,只保留最高阶项 去除最高阶项的系数 时间...
在计算机科学中,时间复杂度用于描述算法执行时间随输入规模增长而变化的趋势。常见的时间复杂度包括O(1)、O(logn)、O(n)、O(nlogn)、O(n²)等,其中O表示数量级的符号。 一般来说,时间复杂度越小,算法的执行效率...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间复杂度等因素。 在实际应用中,数据结构和算法常常是密不可分的。通过对数据结构的理解和运用,以及对算法的学习和...
leetcode怎么计算空间复杂度是指 数据 逻辑关系 线性 非线性 存储关系 顺序 链接 算法 就是求解问题和步骤的序列, 如何描述? 转化成对应的程序语言 一个问题可能有多个 程序就是数据结构加算法 有穷性 确定性 可行...
我们使用体积和边界辛形式之间的最新等效性研究最大柯西切片的体积的边界描述。 已知恒定平均曲率切片的体积与“约克时间”典型地共轭。 在少数示例中,我们使用它来构造与体积共轭的边界变形,例如空的AdS,反向...
动态规划(Dynamic Programming)是一种将复杂问题分解为相对简单的子问题,借助子问题的解来求解原问题的优化算法。它通过记录已解决的子问题的解,避免重复计算,从而...时间复杂度和空间复杂度:该算法的时间复杂度为O(n)
2.2.1 空间复杂度的组成 2.2.2 举例 2.3 时间复杂度 2.3.1 时间复杂度的组成 2.3.2 操作计数 2.3.3 最好、最坏和平均操作计数 2.3.4 步数 第3章 渐近记法 3.1 引言 3.2 渐近记法 3.2.1 大Ο记法 3.2.2 渐近记法Ω和...
3、 掌握算法的基本特性 4、 理解算法效率的评价指标(时间复杂度、空间复杂度),能够评价简单算法的时间复杂度。 二、作业练习: 1、 P10:一、二、三。 P10: 一、 1. 0 1 0 1 2. 集合、线性、树、图 3. 顺序、...
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
从这个角度分析了操作员复杂度随时间的增长,从而在混沌哈密顿量的情况下简单地描述了Lyapunov指数。 复杂性与熵之间的联系是通过有关量子时间估计的量子Fisher信息与冯·诺依曼熵之间的关系表示的。 这种关系表明...
实验课程:算法分析与设计 实验名称:用动态规划法求解资源分配问题 (验证型实验)...时间复杂度为O(n^2*m),空间复杂度为O(n*m),倘若此题只需求最大获利而不必求方案,则状态量可以减少一维,空间复杂度优化为O(n)。
解题思路:要求时间复杂度为o(n),空间复杂度O(1),如果没有这些要求,这题很简单,直接用set去重,遍历数字用字典统计个数,输出个数为1 的key,结束。显然空间复杂度并不满足。 别问我为什么会这题,只能告诉你我...
利用线性变换的思想,提出了布尔矩阵B8n*12n的一种...并给出了该大型布尔矩阵生成算法的具体描述,分析了该算法的时间复杂度,密钥的存储空间。整个求解过程和结果表明该算法的有效性。最后给出了其逆矩阵的求解算法。
目标:*一个解决方案想法*时间和空间复杂度*在编码过程中描述解决方案 第二阶段 中等和审查容易 题数:Leetcode 约 400 题 持续时间:2个月(平均速度:7个解决方案/天) 目标: *找出各种问题的解决方案 *复习简单...
5.掌握计算语句频度和估算算法时间复杂度的方法。 三、基础知识题 1.1 简述下列术语:数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 答:数据是对客观事物的符号表示,在计算机科学中是...
大O可以使我们对算法的时间和空间复杂度有较高的了解。大O只关心总体趋势,而不关注精度。时间/空间复杂度(由Big O衡量)仅取决于算法,而不取决于运行它的硬件。 时间复杂度 大O表示法使我们可以正式谈论算法的...
于篇幅所限,下面只从算法的特性、算法的评价标准和算法的时间复杂度等三个 方面进行介绍。 1.2.1 算法的特性 算法(Algorithm)是对某一特定类型的问题的求解步骤的一种描述,是指令的 有限序列。其中的每条指令表示...
答:空间复杂度和时间复杂度 (27) 数据结构包括数据的逻辑结构、数据的 ______以及对数据的*作运算。 答:存储结构 (28) 一个类可以从直接或间接的祖先中继承所有属性和方法。采用这个方法提高了软件的______。 答...
leetcode104 python-target-offer 备战刷题《剑指offer》python的实现 排序 1、把第一个元素与第二...过程简单描述: 1、从数组第2个元素开始抽取元素。 2、把它与左边第一个元素比较,如果左边第一个元素比它大,则继