我正在尝试使用Big O.计算算法的不同变体的复杂性
算法的简化描述如下：
让我们考虑一个"转换器"，一个接受某个对象并将其转换为另一种表示的函数。每个转换器定义其域和范围。
有一个例程，它获取一个源对象(即要转换的对象)、一个转换器函数列表和预期的转换类型。
它在转换器列表上迭代，直到找到域和范围与要转换的对象和期望的转换类型兼容的转换器。
据我所知，它的复杂性应该是O(n)，因为它直接取决于转换器的数量。
现在，如果每个转换器可能需要递归调用转换例程一定次数，那么复杂度会是多少？
例如，它可能需要将源对象的某些组件转换为其他对象，这些对象稍后将被组装为要返回的对象(原始转换的目标)。
据我所知，这非正式地给出了：
n + m1( n + m2 (n + m3 (...)) ) )
其中：
- n是寻找原始转换器的努力的度量
- m1是应该由转换例程转换的源对象子组件的数量
- m2——原始m1个对象的子组件的最大数量
- 等等
作为额外的细节，每次递归调用时要转换的子组件数量应该减少。
这是正确的吗？如果是，我应该如何将这个公式简化为大O表示法？
最后，如果有一种智能索引系统可以让我在转换器列表中快速找到正确的转换器函数，那么复杂度会是多少？据我所知，在转换器不递归调用转换函数的最简单情况下，应该是O(logn)，对吗？。
但是，如果像前面的情况一样，每个转换器都需要递归调用转换函数，那么基于索引的算法的复杂性会是多少？
据我所知，它的复杂性应该是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。等等。