计算算法使用大O

Question

我试图用大O.计算算法的不同变化的复杂性复杂性

算法的简化描述如下：

让我们考虑一个“转换器”功能这需要某个对象并将其转换为另一个表示。每个转换器都定义了它的域和范围。

有一个例程需要源对象（即要转换的对象），转换器函数列表以及转换的预期类型。

它在转换器列表上进行迭代，直到找到其域和范围与要转换的对象兼容的转换器以及预期的转换类型。

据我所知，它的复杂性应该是O（n），因为它直接取决于转换器的数量。

现在，如果每个转换器可能需要递归地调用转换例程一定次数，那么复杂度如何？

例如，它可能需要将源对象的某些组件转换为稍后将组装为要返回的对象（原始转换的目标）的其他对象。

据我了解，非正式这给：

n + m1(n + m2 (n + m3 (...)))) 

其中：

• n是努力找到原转换器的测量。
• m1应由转换例程转换的源对象子组件的数量。
• m2来自原始m1对象的子组件的最大数量。
• 等...

作为一个额外的细节，子转换应在每个递归调用减少的数量。

这是正确的吗？如果是这样，我应该如何将这个公式缩减为大O符号？

最后，如果有一种智能索引系统使我能够在转换器列表中快速找到正确的转换器功能，那将会是多么的复杂？ 据我所知，在最简单的情况下，一个转换器不会递归调用转换函数，这应该是O（log n），是正确的？

但是，如果每个转换器（如前一种情况）可能需要递归调用转换函数，那么基于索引的算法的复杂度是多少？

Answer 1

据我所知，其复杂性应该是O（n），因为它直接取决于转换器的数量。

不一定。渐近复杂度与您输入的大小（以字节为单位）有关。如果你的对象有一个恒定的大小，那么总输入大小（你的N）将渐近地与转换器的数量成正比，因此迭代它们将是O（N）。另一方面，如果你的对象很大 - 比方说一个m×m的矩阵，其中m是转换器的数量，那么你的N将与m^2成比例并且迭代将是O（m），这仅为O（sqrt（n））。另一个重要的情况是何时转换器的数目受常数的限制，而不是调用者可以设置的高度 - 在迭代为O（1）的情况下。

现在，如果每个转换器可能需要递归地调用转换例程一定次数，那么复杂度如何？

很难说不知道转换器的功能。对于我们所知道的，他们可能会进入一个无限循环，永远不会返回结果。

据我了解，这给

n + m1(n + m2 (n + m3 (...)))) 

不一定，首先，内来电可能不为n，因为对象的大小或转换器列表可能已经改变。

此外，目前你的公式是非正式的。您应该尝试将其转换为真正的重现。

---

再回到你的问题，我得到的印象是，你的对象是一种像节点的一棵树，你遍历这棵树为INT转换成别的东西。在这种情况下，通过查看数据结构而不是尝试重现可能更容易找到复杂性。例如，如果我们知道初始对象的每个节点最终都会被处理一次，那么（假设我们有n个节点），我们的总运行时间将是处理单个节点的成本的n倍。如果处理一个节点由寻找一个转换器所花费的时间占主导地位，则处理节点的复杂度为O（m），其中m是转换器的数量。另一方面，如果处理该节点的成本（在您已经转换子节点之后）大于此值，那么您将忽略查找转换器的代价并使用它。

假设一旦你处理了一个节点，子节点很便宜（比如说恒定时间），那么我们的总时间复杂度就是O（n * m），其中n是节点的数量，m是转换器的数量。现在我们只需要将它转换成以N为单位的东西。如果n和m都是O（n）（taht是，对象和转换器列表都是我们想要的那么大），那么复杂度就是O（N^2 ）。如果对象与我们想要的一样大（n是O（N）），但转换器列表的大小有限（m是O（1）），那么n * m是O（N）。等等。