algorithm - 以下哪个函数不是 O(log(N))

Question

我有一道计算机科学课的多项选择题:

下面哪个函数不是O(log(N))

1. log(log(N))
2. 1000 + log(N)
3. 1000 log(N)
4. log(1000 N)
5. log(N^2)
6. 1000 log(1000 N^1000)
7. 以上都是O(log(N))

哪个是正确答案？

Answer 1

正确的选项是 7 - 每一个都是 O(log(N))。

让我们看看为什么:

1. log(log(N)) - 这比 log(N) 增长得慢，所以技术上你可以说它是 O(log (N))(虽然实际上人们通常会尝试获得最紧的界限，所以你会说它是 O(log(log(N)))。FWIW，你可以甚至说它是 O(N^2) 或 O(N^N)。

2. 1000 + log(N) - 这显然是 O(log(N)) - 请记住常量被丢弃；这里感兴趣的术语是 log(N)。

3. 1000 log(N) - 出于同样的原因，这是 O(log(N))(增长因子是 log( N)，渐近分析中该常数可忽略不计)。

4. log(1000 N) - 同样，常量...

5. log(N^2) - 请记住 log(a^b) 与 b log(a) 相同>，所以 log(N^2) 与 2 log(N) 相同，出于同样的原因，后者是 O(log(N)).

6. 1000 log(1000 N^1000) - 同样，这等同于 10^6 log(1000 N)，即 O(日志(N))。

如果出于某种原因您仍然不确定为什么常量在渐近分析中被丢弃，您可以查看 the formal definition of Big O notation ，但背后的直觉是，随着 N 的增长，常数因子很容易变得(在某些时候)可以忽略不计，因此它们不会产生太大的差异。 Big O 分析的重点是了解算法的运行时间如何随着输入越来越大而增长。