algorithm - 一种算法的时间复杂度级联到另一种算法？

Question

我正在使用随机森林解决监督分类问题，我正在使用 k-means 聚类算法在每个节点拆分数据。我正在尝试计算算法的时间复杂度。据我了解，k-means 的时间复杂度是

O(n · K · I · d )

在哪里

• n是点数，
• K 是簇数，
• I 为迭代次数，
• d 是属性的个数。

k、I、d 是常量或有上限，n 比这三个大得多，所以我想复杂度只是 O(n)。

另一方面，随机森林是一种分而治之的方法，因此对于 n 个实例，复杂度为 O(n · logn)，尽管我对此不确定，如果我错了请纠正我。

为了获得算法的复杂性，我是否只需添加这两个东西？

Answer 1

在这种情况下，您不会将这些值相加。如果你有一个分而治之的算法，运行时间是由以下因素的组合决定的

• 每次调用的子问题数量，
• 这些子问题的规模，以及
• 每个问题完成的工作量。

更改这些参数中的任何一个都会极大地影响函数的整体运行时间。如果每次调用的子问题数量增加一点点，子问题总数就会呈指数级增长，这会对整体产生很大影响。同样，如果你增加每个级别完成的工作，因为有太多的子问题，运行时间可能会大幅波动。查看 Master Theorem 作为示例，了解如何根据这些量确定运行时间。

在您的情况下，您从一个分而治之的算法开始，您所知道的是运行时间为 O(n log n)，并添加了一个步骤，每个级别的工作量为 O(n)。只知道这一点，我不相信可以确定运行时是什么。另一方面，如果您假设

• 该算法总是将输入分成两个较小的部分，
• 该算法独立地递归处理这两个部分，并且
• 该算法使用您的 O(n) 算法来确定进行哪个拆分

那么你可以得出运行时间为 O(n log n) 的结论，因为这是主定理给出的递归的解决方案。

不过，如果没有关于算法内部工作原理的更多信息，我不能肯定地说。

希望这对您有所帮助!