假设您有一个算法，它首先处理 N 个元素，然后是 N 的一半，然后是 N 的四分之一，依此类推。将这种算法的运行时间描述为 O(fibonacci(n)) 而不是 O(n log n) 是否有意义？我想使用斐波那契函数，因为它看起来更具体，另一方面 - 这听起来有争议。
编辑：
抱歉，这似乎是一个有趣的问题，但答案让我意识到我需要一些完全不同的东西:)
user797257
问问题
114 次
4 回答
2
虽然使用O(nlogn)和O(fibonacci(n))在数学上都是正确的 - 因为大 O 表示法只提供渐近上限 - 这个界限不会很紧。
假设您处理的每个元素的O(1)复杂性实际上是函数的复杂性Theta(n)，因为您实际上有：
n + n/2 + n/4 + ... + 1 <= 2n
上面是正确的，因为你实际上有一个几何级数，q=1/2并且n->infinity你得到了 的总和2n。
请注意，由于大 O 表示集合，则ifO(n)是子集O(nlogn)，并且两者都是O(fibonacci(n))-的子集，因此O(n)是在这种情况下使用的最有用和最具体的符号。
于 2013-03-31T13:16:11.983 回答
2
N + 1/2 N + 1/4 N + 1/8 N + .... 大约 2 N :) 所以如果处理一个项目是 O(1)，复杂度仍然是 O(N)。
于 2013-03-31T13:17:31.523 回答
1
只要其他人知道你的意思，你就可以写任何你想写的东西。
也就是说，与 相比，它的写作要少得多，因为没有多少人O(n logn)会O(fibonacci(n))知道您使用第二种表示法的意思。
此外，fibonacci(n) 可以很容易地被认为是指斐波那契序列的第 n 个元素。
于 2013-03-31T13:16:17.233 回答
0
不，它不会。计算机科学中大 O 表示法 的全部意义在于提供算法成本的渐近限制，但有些草率。因此，例如，我们忽略了几乎每次使用O(x). 类似地，我们假设在分析中建模的每个操作都是等价的，除了在罕见的、特定的情况下（例如，在某些密码计算中使用的任意精度算术）。 我们的目标不是精确，而是一种易于理解的共同理解。
于 2013-03-31T14:05:16.270 回答