0

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

O(n·K·I·d)

在哪里

  • n 是点数，
  • K是集群的数量，
  • I 是迭代次数，并且
  • d 是属性的数量。

k、I 和 d 是常数或有上限，并且 n 与这三个相比要大得多，所以我认为复杂度只是 O(n)。

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

为了获得算法的复杂性，我只需添加这两件事吗？

4

1 回答 1

1

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

  • 每次调用产生的子问题数，
  • 这些子问题的大小，以及
  • 每个问题完成的工作量。

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

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

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

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

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

希望这可以帮助！

于 2013-10-26T02:11:55.453 回答