1

我有一个在 O(m) 时间内运行的算法。该算法接收一组包含 m 个条目的数据。

通过指定严格的正整数输入 n 随机生成数据。生成的条目数为 O(n log n)。

编辑

单独生成数据的时间复杂度与 n（或 O(1)）无关，这意味着给定整数 n，条目是立即随机生成的。结果条目的数量是随机的，但为 O(n log n)。例如 n = 10，则生成的条目数是某个常数乘以 10（log 10）。

数据是事先生成的。然后将得到的 m 个条目作为输入馈送到算法中。

问题

然后我可以假设算法在 O(n log n) 时间内运行吗？

4

1 回答 1

2

您的问题中有一些模棱两可的地方，要么是故意放置以帮助您内化输入大小和运行时间复杂度之间的关系，要么是由于沟通不畅而导致的。

因此，尽我所能解释这种情况：

您的算法复杂度与 m 成O(m)线性关系。

因此，由于We assume that generating the data is independent of input. i.e. O(1).，您的时间复杂性仅取决于n您指定的生成条目的一些内容。

所以是的，你可以说算法O(n log n)及时运行，因为它对 size 的输入没有任何作用m。

针对您更新的问题：

仍然很难理解，因为一些关键词指的是不同的事物。但总的来说，我认为这就是你所得到的：

  • 您有一个数据集作为输入，即大小为 O(n log n)，给定一些特定的 n。
  • 该数据集仅用作输入，它要么是预先生成的，要么是使用在 O(1) 时间内运行的某个黑盒生成的，而不管黑盒的 n 是多少。（我们对这个问题的黑匣子不感兴趣）
  • 然后将该数据集输入到我们真正感兴趣分析的算法中。
  • 对于大小为 m 的输入，该算法的时间复杂度为 O(m)。
  • 由于您的输入相对于 n 的大小为 O(n log n)，因此通过扩展，您的 O(m) 线性时间算法相对于 n 的时间复杂度为 O(n log n)。

要查看差异：假设您的算法不是线性的，而是二次 O(m^2)，那么它相对于 n 的时间复杂度为 O(n^2 log^2 n)。

于 2012-12-03T18:26:31.440 回答