以下哪个函数不是 O(log(N))
Which of the following functions is not O(log(N))
我有一道计算机科学的选择题class:
下面哪个函数不是O(log(N))
log(log(N))1000 + log(N)1000 log(N)log(1000 N)log(N^2)1000 log(1000 N^1000)- 以上都是
O(log(N))
哪个是正确答案？
正确的选项是 7 - 每一个都是 O(log(N))。
让我们看看原因：
log(log(N)) - 这比 log(N) 增长得慢，所以从技术上讲，你可以说它是 O(log(N))（尽管实际上人们通常会尝试获得最紧绑定，所以你会说它是 O(log(log(N)))。 FWIW，你甚至可以说它是 O(N^2) 或 O(N^N).
1000 + log(N) - 这显然是 O(log(N)) - 记住常量被丢弃；这里感兴趣的术语是 log(N).
1000 log(N)——同理，这里是O(log(N))（增长因子是log(N)，这个常数在渐近分析中可以忽略不计）。
log(1000 N) - 同样，常量...
log(N^2) - 请记住 log(a^b) 与 b log(a) 相同，因此 log(N^2) 与 2 log(N) 相同出于同样的原因 O(log(N)).
1000 log(1000 N^1000) - 同样，这等同于 10^6 log(1000 N) 即 O(log(N))。
如果出于某种原因你仍然不确定为什么在渐近分析中常数被丢弃，你可以看看 the formal definition of Big O notation，但背后的直觉是随着 N 的增长，常数因素很容易变得（在某些时候）可以忽略不计，因此它们不会产生太大的影响。大 O 分析的重点是了解算法的 运行 时间如何随着输入越来越大而增长。
我有一道计算机科学的选择题class:
下面哪个函数不是O(log(N))
log(log(N))1000 + log(N)1000 log(N)log(1000 N)log(N^2)1000 log(1000 N^1000)- 以上都是
O(log(N))
哪个是正确答案？
正确的选项是 7 - 每一个都是 O(log(N))。
让我们看看原因：
log(log(N))- 这比log(N)增长得慢，所以从技术上讲，你可以说它是O(log(N))（尽管实际上人们通常会尝试获得最紧绑定，所以你会说它是O(log(log(N)))。 FWIW，你甚至可以说它是O(N^2)或O(N^N).1000 + log(N)- 这显然是O(log(N))- 记住常量被丢弃；这里感兴趣的术语是log(N).1000 log(N)——同理，这里是O(log(N))（增长因子是log(N)，这个常数在渐近分析中可以忽略不计）。log(1000 N)- 同样，常量...log(N^2)- 请记住log(a^b)与b log(a)相同，因此log(N^2)与2 log(N)相同出于同样的原因O(log(N)).1000 log(1000 N^1000)- 同样，这等同于10^6 log(1000 N)即O(log(N))。
如果出于某种原因你仍然不确定为什么在渐近分析中常数被丢弃，你可以看看 the formal definition of Big O notation，但背后的直觉是随着 N 的增长，常数因素很容易变得（在某些时候）可以忽略不计，因此它们不会产生太大的影响。大 O 分析的重点是了解算法的 运行 时间如何随着输入越来越大而增长。