时空复杂度

时间复杂度

时间复杂度是描述算法运行的时间。我们把算法需要运算的次数用输入大小为 n 的函数来表示， 计作 T(n)。时间复杂度通常用 O(n)来表示，公式为 T(n)=O(f(n)),其中 f(n) 表示每行代码的执行次数之和，注意是执行次数。

对算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。 另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

下面按从快到慢的顺序列出了经常会遇到的 5 种大 O 运行时间。

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，快速排序——一种速度较快的排序算法。
• O(n2)
• O(n!)

空间复杂度

空间复杂度是对算法运行过程中临时占用空间大小的度量，一个算法所需的存储空间用 f(n)表 示，可得出 S(n)=O(f(n)),其中 n 为问题的规模，S(n)表示空间复杂度。通常用 S(n) 来定义。

• O (1)：算法执行所需要的临时空间不随着某个变量 的大小而变化，即此算法空间复杂度为一个常量， 可表示为 O(1)
• O (n)

const arr = new Array(n);

时间空间相互转换

对于一个算法来说，它的时间复杂度和空间复杂度往往是相互影响的。

当追求一个较好的时间复杂度时，可能需要消耗更多的储存空间。 反之，如果追求较好的空间复杂度，算法执行的时间可能就会变长.