数据结构中的时空复杂性

算法分析

可以在实施之前和实施之后的两个不同阶段进行算法效率分析,如下

先验分析-这被定义为算法的理论分析。通过假设所有其他因素(例如处理器速度)是恒定的,并且对实现没有影响,来衡量算法的效率。

后验分析-定义为算法的经验分析。所选算法是使用编程语言实现的。接下来,所选算法在目标计算机上执行。在此分析中,收集了诸如运行时间和所需空间之类的实际统计信息。

算法分析涉及所涉及的各种操作的执行或运行时间。一项操作的运行时间可以定义为每项操作执行的计算机指令的数量。

算法复杂度

假设X被视为一种算法,而N被视为输入数据的大小,则算法X所实现的时间和空间是决定X效率的两个主要因素。

时间因子-通过计算关键操作(例如排序算法中的比较)的数量来计算或测量时间。

空间系数-通过计算算法所需的最大内存空间来计算或测量空间。

算法的复杂度f(N)提供了算法所需的运行时间和/或存储空间(相对于N作为输入数据的大小)。

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的存储空间量。

算法所需的空间等于以下两个组成部分的总和

固定部分是存储某些数据和变量(即简单变量和常量,程序大小等)所需的空间,而这些数据和变量与问题的大小无关。

可变部分是变量所需的空间,其大小完全取决于问题的大小。例如,递归堆栈空间,动态内存分配等。

任何算法p的空间复杂度S(p)为S(p)= A + Sp(I)其中A被视为固定部分,而S(I)被视为算法的可变部分,具体取决于实例特征I以下是一个简单的示例,试图解释该概念

算法

SUM(P, Q)
Step 1 - START
Step 2 - R ← P + Q + 10
Step 3 - Stop

这里我们有三个变量P,Q和R和一个常数。因此,S(p)= 1 + 3。现在,空间取决于给定常量类型和变量的数据类型,并且它将相应地相乘。

时间复杂度

算法的时间复杂度是算法执行完成所需要的时间量的表示。时间要求可以表示为或定义为数值函数t(N),其中t(N)可以作为步数进行测量,前提是每一步需要固定的时间。

例如,在将两个n位整数相加的情况下,采取N步。因此,总的计算时间为t(N)= c * n,其中c是两个位相加所消耗的时间。在这里,我们观察到t(N)随着输入大小的增加而线性增长。