不同的参数如何影响时间复杂度的大O表示法
不同的参数如何影响时间复杂度的大O表示法
提问于 2020-07-02 10:50:26
例如，如果我在我的方法中有两个参数M和N，并且时间复杂度被证明是O(M+N)，为什么人们说O(M+N)而不是O(N)，O(N)是O(2N)的简化形式？什么时候我们应该在大O符号中使用多个变量？这背后有什么道理吗？传递给参数的不同变量将如何影响增长率，为什么不将它们组合成一个大O变量？我想不出哪一个实例中传入的不同变量参数会影响运行时。我刚开始接触数据结构和算法，所以我想知道。
回答 2
Stack Overflow用户
发布于 2020-07-02 12:49:59
时间复杂度表示运行时如何随输入大小的变化而变化。
传递给该方法的2个变量表示输入的大小，它们都是2个不同的维度。
如果为M >>> N，则O(M + N)等同于O(M)；如果为N >>> M，则O(M + N)等同于O(N)。
只有当M ~ N，即时间复杂度= O(2*N)或O(2*M)，相当于O(N)或O(M)时，我们才能将M和N结合起来。
另外，O(M + N)是一种精确的表示时间复杂度的方法，它兼顾了M和N约束的上述3种情况。
Stack Overflow用户
发布于 2020-07-02 13:37:27
老实说，大O符号是一种近似。因为O(N*N + N)被认为是O(N*N)。然而，这是一个标准的规则，算法的整体大O符号等同于它最慢的部分。
示例
如果一个算法的复杂度是O(N + logN)，那么它必须写成O(N)复杂度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62688208
复制相关文章
相似问题
腾讯云开发者
