数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究数据结构中的时间和空间复杂度
算法分析
算法效率的分析可以在两个不同的阶段进行，即实现之前和实现之后，如下所示：
先验分析 - 这被定义为算法的理论分析。通过假设所有其他因素（例如处理器的速度）都是恒定且对实现没有影响来衡量算法的效率。
后验分析 - 这被定义为算法的经验分析。所选择的算法使用编程语言实现。接下来，所选择的算法在目标计算机上执行。在此分析中，会收集实际统计数据，例如运行时间和所需空间。
算法分析处理的是各种操作的执行或运行时间。操作的运行时间可以定义为每个操作执行的计算机指令数。
算法复杂度
假设 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) 随着输入大小的增加而线性增长。
49K+ 浏览量
