为什么O（1）！= O（日志（N））？对于n = [整型，长，...] [英] why O(1) != O(log(n)) ? for n=[integer, long, ...]

问题描述

举例来说，假设N = Integer.MAX_VALUE的或2 ^ 123，然后为O（log（N））= 32和123这样一个小的整数。是不是O（1）？

for example, say n = Integer.MAX_VALUE or 2^123 then O(log(n)) = 32 and 123 so a small integer. isn't it O(1) ?

有什么区别？我认为，其原因是O（1）是恒定的，但O（日志（N））没有。任何其他的想法？

what is the difference ? I think, the reason is O(1) is constant but O(log(n)) not. Any other ideas ?

推荐答案

如果 N 上面是有界的，那么涉及到复杂类 N 并没有什么意义。有没有这样的事情，在限制为2 ^ 123接近无穷大，除了在老笑话说：五边形接近了一圈，为5足够大的价值。

If n is bounded above, then complexity classes involving n make no sense. There is no such thing as "in the limit as 2^123 approaches infinity", except in the old joke that "a pentagon approximates a circle, for sufficiently large values of 5".

通常，当分析的code复杂性，我们pretend该输入大小不是上述围边机器的资源限制，即使它是。这的确导致了一些稍微奇怪的事情会围绕为log N ，因为如果 N 必须适应一个固定大小的int类型，那么日志N 有相当小的束缚，所以绑定的更可能是有用/相关的。

Generally, when analysing the complexity of code, we pretend that the input size isn't bounded above by the resource limits of the machine, even though it is. This does lead to some slightly odd things going on around log n, since if n has to fit into a fixed-size int type, then log n has quite a small bound, so the bound is more likely to be useful/relevant.

所以有时候，我们要分析的算法略有理想化的版本，因为实际的code写的不能接受任意大的输入。

So sometimes, we're analysing a slightly idealised version of the algorithm, because the actual code written cannot accept arbitrarily large input.

例如，一般的快速排序正式采用的Theta（log n）的叠加，在最坏的情况下，显然这样的相当普遍的实现，呼叫递归上的分区和环路递归的小侧大 侧​​。但在32位计算机上，你可以安排在实际上使用约240字节的固定大小的数组来存储待办事项列表，这可能是少于你基于一种算法，正式为O写了一些其他的功能（1）堆栈使用。道德是实现！=算法复杂度不告诉你小数目任何东西，任何特定的号码是小。

For example, your average quicksort formally uses Theta(log n) stack in the worst case, obviously so with the fairly common implementation that call-recurses on the "small" side of the partition and loop-recurses on the "big" side. But on a 32 bit machine you can arrange to in fact use a fixed-size array of about 240 bytes to store the "todo list", which might be less than some other function you've written based on an algorithm that formally has O(1) stack use. The morals are that implementation != algorithm, complexity doesn't tell you anything about small numbers, and any specific number is "small".

如果你想占为界，你的可以的说，例如，你的code到一个数组排序是O（1）运行时间，因为数组必须低于适合在PC的地址空间的大小，并且因此时间整理它是有界的。但是，你会如果你失败你的CS任务，你将不会被任何人提供任何有用的信息： - ）

If you want to account for bounds, you could say that, for example, your code to sort an array is O(1) running time, because the array has to be below the size that fits in your PC's address space, and hence the time to sort it is bounded. However, you will fail your CS assignment if you do, and you won't be providing anyone with any useful information :-)

这篇关于为什么O（1）！= O（日志（N））？对于n = [整型，长，...]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！