有没有什么功能是O（1）？ [英] Is there any function that is in o(1)?

问题描述

我的一位同事问我一个问题：是集 O（1）（小O符号）空？

A colleague of mine has asked me a question: Is the set o(1) (little o notation) empty?

我的问题是： O（1）空集？如果没有，是否有程序，有 O（1）时间复杂度？

My question is: Is o(1) an empty set? If not, is there a program that has o(1) time complexity?

提醒，小邻为<定义href="http://syedwaqarahmad.webs.com/documents/t._cormen_-_introduction_to_algorithms_3rd_edition.pdf">Cormen:

一个函数 F（N）据说是在 O（G（N））如果任何正   恒 C＆GT; 0 ，存在一个常数 N0＆GT; 0 ，使得 0℃= F（N）＆LT; CG（N），所有 N'GT;。= N0

A function f(n) is said to be in o(g(n)) if for any positive constant c>0, there exists a constant n0 > 0 such that 0 <=f(n) < cg(n) , for all n>= n0.

直观地说，如果 F（N）是 O（G（N））如果是在 O（G（N）），但这个束缚不紧。

Intuitively, if f(n) is in o(g(n)) if it is in O(g(n)), but this bound is NOT tight.

推荐答案

设置的 O（1）不为空

The set o(1) is not empty.

这是第一重要的是要记住，函数f（x）是 O（G（X））如果且仅当

It is first important to remember that f(x) is in o(g(x)) if and only if

lim_x->无限{F（X）/ G（x）} = 0   
对于非零G（X）

lim_x->infinity { f(x) / g(x)} = 0
For non zero g(x)

但是，更重要的，什么是候选的函数f（x）？

But, more important, what is the set of candidate f(x)?

在所有真正的功能 ^{[1] ，即 F：R-＆GT; RU {蓝} （其中U是未定义的函数的一些值）。这意味着，我们可以使用任何真正的现实功能，包括函数 F（X）= 1 / X 。 我们也可以看到， G（X）= 1 是一个非零的功能，而事实上：}

Some define it over all real functions ^[1], i.e. f:R->RU{U} (Where U is undefined for some values of the functions). This means, we can use any real to real function, including the function f(x)=1/x. We can also see that g(x)=1 is a non zero function, and indeed:

lim_x->无限{1 / X / 1} = 0

lim_x->infinity { 1/x / 1} = 0

这意味着， O（1）包括函数 F（X）= 1 / X ，和我们可以断定该集是没有空。
克努特也指功能 G（N）= N ^ -1 作为一个有效的功能，并使用为O（n ^ -1） 在他的解释大O，欧米茄和西塔的（1976）

This means, o(1) includes the function f(x)=1/x, and we can conclude the set is none empty.
Knuth also refers the function g(n) = n^-1 as a valid function, and uses O(n^-1) in his explanation of big O,Omega and Theta (1976)

其他，Cormen就是其中之一，定义一套为f：N-> N，其中N = {0,1，...}，这也包括 F（X）= 0 ，这又持有条件是O（1）。 ^[2]

Others, Cormen is one of them, define the set as f:N->N, where N={0,1,...}, and this also includes f(x)=0, which again holds the condition for being o(1).^[2]

没有算法的复杂度功能 T（N）在 O（1）

There is no algorithm with complexity function T(n) in o(1)

虽然有点O符号的定义在实数，我们的复杂功能的算法都没有。它们是定义在自然数 ^[3] 。你要么做指导，或不。你不能做一个指令，或电子 ¹ 指令的一半。这意味着，该组的复杂功能 F：N-＆GT; N 。由于没有这样的事情空计划，有没有说明书（召回在调用它本身所花费的时间）的开销，甚至缩小这个范围 F：N-＆GT; N \ {0}

While little o notation is defined over reals, our complexity functions for algorithms are not. They are defined over natural numbers ^[3]. You either do the instruction, or don't. You cannot do half of an instruction, or e^-1 instruction. This means, the set of complexity functions are f:N->N. Since there is no such thing as "empty program" that has no instructions (recall that the overhead of calling it itself takes time), it even narrows this range to f:N->N\{0}.

换句话说，对于算法的任何复杂功能 T（N），并为所有 N'GT; 0 ， T（N）大于0 。

In other words, for any complexity function of an algorithm T(n), and for all n>0, T(n)>0.

现在我们可以回到我们的公式：

We can now go back to our formula:

lim_x->无限{T（X）/ 1}> = lim_x->无限{1/1} = 1> 0

lim_x->infinity { T(x) / 1} >= lim_x->infinity { 1 / 1} = 1 > 0

这说明我们有O（1）在没有积极性功能，我们可以得出结论：没有任何算法具有复杂功能是在 O（1）。

This shows us there is no positive natural function in o(1), and we can conclude no algorithm has a complexity function that is in o(1).

脚注：
（1）如果你不确定它，召回泰勒级数，在某些时候，我们停止增加了无穷级数，只是提到它是 O（X ^ N）。在这个大O符号，我们隐藏功能是不是在自然数。
（2）如果我们定义但集合N + = {1,2，...}是组正自然数的和O（G（N））是积极的自然功能的一个子集，邻（1）是一个空集，以证明等同于一个显示没有算法具有这种复杂性。
（3）好了，对于一般情况下，图像可以是非自然数，但我们会假定最坏情况下的复杂性在这里，虽然索赔仍然可以按住一般情况下，由于没有空的程序。

Foot Notes:
(1) If you are unsure about it, recall in Taylor series, at some point we stop adding the infinite series, and just mention it is O(x^n). The function we "hide" in this big O notation is not over the natural numbers.
(2)If we however define the set N+={1,2,...} to be the set of positive natural numbers, and o(g(n)) to be a subset of positive natural functions, o(1) is an empty set, with a proof identical to the one showing no algorithm has this complexity.
(3) Well, for average cases, the image can be a non natural number, but we'll assume worst case complexity here, though the claim can still hold for average case, since there is no empty program.

这篇关于有没有什么功能是O（1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！