数据结构和算法中的时间复杂度分析
Time complexity analysis in data structures and algo
我们能否将 O(m+n) 与 O(n) 进行比较，因为我们只需要关注最高功率，所以它们是相同的？
O(m+n) 和 O(n) 的复杂度都与输入 n 成线性关系。相对于m，O(m+n)的复杂度是线性的，而O(n)是常数。
因此，除非我们仅分析输入 n 并假设 m 为常数，否则我们通常无法将 O(m+n) 简化为 O(n)。
有时我们可以将两个输入维度合并为一个：例如，如果 m 是输入字符串的数量，n 是输入字符串的最大长度，那么我们可以通过分析与所有输入字符串的总长度。
O(m+n) 是 two-dimensional（它必须有参数 m 和 n），如果没有更多信息，您不能将它缩小到一维关于m和n的关系
具体例子：很多图算法（如深度优先搜索、拓扑排序）的时间复杂度为O(v + e) ，其中 v 是顶点数，e 是边数。您可以考虑两种不同类型的图表：
在有很多边的稠密图中，e 与 v² 成正比。该算法在这类图上的时间复杂度为 O(v + v²), 或者 O(v²).
在边很少的稀疏图中，e与v成正比。该算法在这类图上的时间复杂度为 O(v + v), 或者 O(v).
我们能否将 O(m+n) 与 O(n) 进行比较，因为我们只需要关注最高功率，所以它们是相同的？
O(m+n) 和 O(n) 的复杂度都与输入 n 成线性关系。相对于m，O(m+n)的复杂度是线性的，而O(n)是常数。
因此，除非我们仅分析输入 n 并假设 m 为常数，否则我们通常无法将 O(m+n) 简化为 O(n)。
有时我们可以将两个输入维度合并为一个：例如，如果 m 是输入字符串的数量，n 是输入字符串的最大长度，那么我们可以通过分析与所有输入字符串的总长度。
O(m+n) 是 two-dimensional（它必须有参数 m 和 n），如果没有更多信息，您不能将它缩小到一维关于m和n的关系
具体例子：很多图算法（如深度优先搜索、拓扑排序）的时间复杂度为O(v + e) ，其中 v 是顶点数，e 是边数。您可以考虑两种不同类型的图表：
在有很多边的稠密图中，e 与 v² 成正比。该算法在这类图上的时间复杂度为 O(v + v²), 或者 O(v²).
在边很少的稀疏图中，e与v成正比。该算法在这类图上的时间复杂度为 O(v + v), 或者 O(v).