时间复杂度的可加性? [英] Additivity of time complexity?

问题描述

我目前正在为学校开展一个项目，在该项目中我有时间复杂度限制.我还在开始学习编程，所以这个问题的道歉是愚蠢的.

I'm currently working on a project for school in which I have a time complexity restriction. I'm still beginning to learn to program so apologies of this question is stupid.

本质上，假设我有一个约束，即我的程序必须满足时间复杂度 O(n^2 + mlogm)，其中 n 和 m 是一些输入大小.这是否意味着这是我的程序的任何特定组件可以运行的最大时间复杂度?也就是说，如果我有大量的 O(n^2 + m) 函数，但最复杂的函数在 O(n^2 + mlogm) 中运行，我还能满足这个时间限制吗?例如，如果我的程序按顺序运行以下函数

Essentially, lets say I have a constraint that my program must satisfy the time complexity O(n^2 + mlogm), where n and m are some sizes of input. Does that mean that's the maximum time complexity any specific component of my program can run in? That is, if I have a ton of, say, O(n^2 + m) functions, but the most complex function runs in O(n^2 + mlogm), will I still satisfy this time bound? For example, if my program runs the following functions in order

函数A

函数B

函数C

函数D

而且函数A、B、C都是O(n^2+m)或者小于时间复杂度约束的东西，但是最后一个函数是O(n^2+mlogm)，我的程序会在时间之内吗约束?对于整体复杂性，这不是 O(n^2 + m ^ n^2 + m ^ n^2 + m + n^2 + mlogm) 吗?

And functions A, B, C are all O(n^2 + m) or something less than the time complexity restraint, but the last function is O(n^2 + mlogm), will my program be within the time constraint? Would that not somehow be O(n^2 + m ^ n^2 + m ^ n^2 + m + n^2 + mlogm) for the overall complexity?

我仍在学习时间复杂度，因此非常感谢您对此的任何帮助.非常感谢.

I'm still learning about time complexity, so any help for this would be much appreciated. Thanks a bunch.

推荐答案

如果您按顺序执行不同的功能，您只需选择最差复杂度，这就是整体复杂度.

If you're executing different functions in sequence, you just choose the worst complexity and that's the overall complexity.

例如，如果 fnA 是 O(n) 而 fnB 是 O(nn!)，那么 fnA 的任何效果都将被 fnB 完全淹没，假设它们'按顺序运行(非嵌套).

For example, if fnA was O(n) and fnB was O(nn!), then any effect of fnA would be totally swamped by fnB, assuming they're run sequentially (not nested).

在你的情况下，你的函数的最后一个满足要求，前三个更好，所以整体复杂度是最后一个.

In your case, the final of your functions meet the requirement and the first three are better, so the overall complexity is that of the final one.

这篇关于时间复杂度的可加性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！