有没有O（1 / n）algorithm？
有没有O（1 / n）algorithm？
或者是小于O（1）的其他东西？
这个问题并不像看起来那么愚蠢。 至less在理论上，当我们对大O符号进行math定义时，诸如O （1 / n ）这样的东西是完全合理的：
现在你可以很容易用g （ x ）代替1 / x …很明显，上面的定义对于某些f仍然适用。
为了估计渐近的运行时间增长，这是不太可行的…一个有意义的algorithm不能随着input的增长而变得更快。 当然，你可以构造一个任意的algorithm来实现这个，比如下面的algorithm：
def get_faster(list): how_long = (1 / len(list)) * 100000 sleep(how_long) 显然，随着input大小的增长，这个函数花费的时间会更less……至less在硬件（数字的精度， sleep可以等待的最小时间，处理参数的时间等）的某些限制之前，这个限制会是一个恒定的下限，所以实际上上面的函数仍然有运行时O （1）。
但实际上有一些真实世界的algorithm，当input大小增加时，运行时可以减less（至less部分）。 请注意，这些algorithm不会在O （1）之下显示运行时行为。 不过，他们很有趣。 例如， Horspool采用非常简单的文本searchalgorithm。 在这里，随着search模式的长度的增加，预期的运行时间将会减less（但是增加草垛的长度将再次增加运行时间）。
是。
运算符O（1 / n）恰好有一个algorithm，即“空”algorithm。
对于一个algorithm是O（1 / n）意味着它执行的步骤比由单个指令组成的algorithm渐进地less。 如果所有n> n0的执行次数less于一步，则对于那些n必须完全没有指令。 由于检查'n> n0'是否至less需要1条指令，所以它必须不包含所有n的指令。
总结：唯一的algorithm是O（1 / n）是空algorithm，由无指令组成。
这是不可能的。 大O的定义是不等于不等于 ：
A(n) = O(B(n)) <=> exists constants C and n0, C > 0, n0 > 0 such that for all n > n0, A(n) <= C * B(n)
所以B（n）实际上是最大值，因此如果它随着n的增加而减小，则估计不会改变。
锐利是正确的，O（1）是最好的performance。 然而，这并不意味着一个快速的解决scheme，只是一个固定的时间解决scheme。
一个有趣的变种，也许真正build议的是随着人口的增长，哪些问题变得更容易 。 我可以想到1，尽pipe人为地和口头上的回答：
一组中的任何两个人有同样的生日吗？ 当n超过365时，返回true。 虽然less于365，这是O（n ln n）。 也许不是一个好的答案，因为这个问题并没有慢慢变得简单，只是当n> 365时变成了O（1）。
从我之前学习的大O符号，即使你需要1步（如检查variables，做一个任务），也就是O（1）。
请注意，O（1）与O（6）相同，因为“常数”并不重要。 这就是为什么我们说O（n）和O（3n）一样。
所以，如果你只需要1步，那就是O（1）…而且由于你的程序至less需要1步，所以最小的algorithm可以是O（1）。 除非我们不这样做，否则是O（0），我想呢？ 如果我们做任何事情，那么它就是O（1），这是最小的可能。
（如果我们select不这样做，那么它可能成为一个禅或陶的问题……在编程领域，O（1）仍然是最小的）。
或者如何呢：
程序员 ：老板，我find了一个办法，在O（1）时间！
老板 ：不需要这样做，今天早上我们破产了。
程序员 ：哦，那么它变成了O（0）。
怎么没有运行的function（NOOP）？ 或使用固定值。 这算不算？
我经常用O（1 / n）来描述随着投入变大而变小的概率 – 例如，在log2（n）翻转时，公平硬币出现尾部的概率是O（1 / n）。
O（1）只是意思是“恒定时间”。
当你把一个O（1）algorithm转换成O（n），但是使它更快时，
诀窍是一般的恒定时间algorithm是最好的，线性比指数更好，但是对于less量的n，指数algorithm实际上可能更快。
1：假设这个例子有一个静态列表长度
不，这是不可能的：
当n趋于1 / n的无穷大时，我们最终达到1 /（inf），这实际上是0。
因此，这个问题的大哦类将是O（0）有一个大量的n，但更接近恒定的时间与低n。 这是不明智的，因为唯一能够以比定时快的速度完成的事情是：
void nothing() {};
即使这是有争议的！
只要你执行一个命令，你至less在O（1），所以不，我们不能有一个很大的O（1 / n）类！
我相信量子algorithm可以通过叠加“一次”完成多个计算。
我怀疑这是一个有用的答案。
对于阅读这个问题并想了解谈话内容的人来说，这可能会有所帮助：
| | constant | logarithmic | linear | N-log-N | quadratic | cubic | exponential | | n | O(1) | O(log n) | O(n) | O(n log n) | O(n^2) | O(n^3) | O(2^n) | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | | 2 | 1 | 1 | 2 | 2 | 4 | 8 | 4 | | 4 | 1 | 2 | 4 | 8 | 16 | 64 | 16 | | 8 | 1 | 3 | 8 | 24 | 64 | 512 | 256 | | 16 | 1 | 4 | 16 | 64 | 256 | 4,096 | 65536 | | 32 | 1 | 5 | 32 | 160 | 1,024 | 32,768 | 4,294,967,296 | | 64 | 1 | 6 | 64 | 384 | 4,069 | 262,144 | 1.8 x 10^19 |
很多人都有正确的答案（否）下面是另一种certificate它的方法：为了有一个函数，你必须调用函数，并且你必须返回一个答案。 这需要一定的时间。 即使其余的处理花费较less的时间来处理较大的input，打印出答案（我们可以假定为单个位）至less需要一定的时间。
Aunt Wiki提供的函数及其O（）命令列表 。
如果存在解决scheme，可以立即准备和访问。 例如使用LIFO数据结构，如果你知道sorting查询是相反的顺序。 然后，数据已经sorting，因为select了适当的模型（LIFO）。
随着人口增长，哪些问题变得更容易？ 一个答案就是像下载速度是节点数的反函数那样的bittorrent。 与汽车相反，加载速度越慢，像BT这样的文件共享networking也会加速连接的节点越多。
你不能低于O（1），但是O（K）其中K小于N是可能的。 我们称之为次线性时间algorithm 。 在一些问题中，次线性时间algorithm只能给出一个特定问题的近似解。 然而，有时候，一个近似的解决scheme是很好的，可能是因为数据集太大，或者计算所有的计算太昂贵。
O（1 / n）不小于O（1），它基本上意味着你拥有的数据越多，algorithm就越快。 假设你得到一个数组，并且总是填充到10 100个元素，如果它less了那么多，如果有更多的元素，什么也不做。 这当然不是O（1 / n），但是像O（-n）:)太糟糕的O-not notation不允许负值。
正如已经指出的那样，除了空函数的可能的例外之外，可能不存在O(1/n)函数，因为所花费的时间将不得不接近0。
当然，还有一些algorithm，就像Konrad所定义的algorithm一样，至less在某种意义上它们应该小于O(1) 。
def get_faster(list): how_long = 1/len(list) sleep(how_long)
如果你想研究这些algorithm，你应该定义自己的渐近测量，或者你自己的时间概念。 例如，在上面的algorithm中，我可以允许使用一定数量的“空闲”操作。 在上面的algorithm中，如果我通过排除除睡眠以外的所有事物的时间来定义t'，则t'= 1 / n，即O（1 / n）。 可能有更好的例子，因为渐近行为是微不足道的。 事实上，我确信外面的人可以拿出一些不重要的结果。
其余大部分答案将big-O解释为algorithm的运行时间。 但是由于这个问题没有提到，所以我认为值得一提的是在数值分析中大O的另外一个应用，就是错误。
许多algorithm可以是O（h ^ p）或O（n ^ { – p}），这取决于你是在谈论步长（h）还是分割数（n）。 例如，在欧拉方法中 ，假设您知道y（0）和dy / dx（y的导数），则查找y（h）的估计值。 因此，为了find某个任意x的y（x），我们把0到x的区间分开，直到n个碎片，并运行欧拉方法在每个点上，从y（0）到y（x / n）到y（2x / n），依此类推。
因此，欧拉方法是O（h）或O（1 / n）algorithm，其中h通常被解释为步长，n被解释为分割间隔的次数。
由于浮点舍入误差 ，您也可以在实际数值分析应用程序中使用O（1 / h）。 您设置的时间间隔越小，执行某些algorithm的取消就越多，有效数字丢失的次数也会越多，因此会通过algorithm传播的错误也会越多。
对于欧拉方法，如果您使用的是浮点数，请使用足够小的步长和取消数，并且将大数添加到较大数字，而不改变大数。 对于通过从两个非常接近的位置处评估的函数中相互减去两个数字来计算导数的algorithm，使用（y（x + h）-y（x）/ h）近似y'（x） （x + h）接近于y（x），导致较大的抵消，并估计具有较less有效数字的导数。 这又将传播到你需要的任何algorithm的衍生物（例如，边界值问题）。
好的，我想了一下，也许有一个algorithm可以遵循这个一般forms：
您需要计算1000个节点图的旅行推销员问题，但是，还会给出您无法访问的节点列表。 随着无法访问的节点列表越来越大，问题变得更容易解决。
那这个呢：
void FindRandomInList(list l) { while(1) { int rand = Random.next(); if (l.contains(rand)) return; } }
随着列表大小的增长，程序的预期运行时间会减less。
我看到一个algorithm是O（1 / n）不可否认的上限：
你有一系列的input，由于例行程序外部的事情而改变（也许它们反映的是硬件，或者甚至可能是处理器中的某个其他核心），你必须select一个随机但有效的input。
现在，如果没有改变，你只需要制作一个项目清单，随机挑选一个，得到O（1）次。 但是，数据的dynamic性排除了列表，您只需要随机地进行探测并testing探针的有效性。 （并且注意，固有的答案在返回时仍然是无效的，但仍然可以使用 – 比如说一个游戏中的单位AI，它可以在一个目标落到视线之外拉动扳机。）
这种情况的最坏情况是无穷大，但是随着数据空间的填充，平均情况下性能下降。
在数值分析中，近似公差中近似algorithm应该具有次恒定的渐近复杂性。
class Function { public double[] ApproximateSolution(double tolerance) { // if this isn't sub-constant on the parameter, it's rather useless } }
我在2007年有这样的疑问，很高兴看到这个线程，我从我的reddit线程来到这个线程 – > http://www.reddit.com/r/programming/comments/d4i8t/trying_to_find_an_algorithm_with_its_complexity/
有可能构build一个O（1 / n）的algorithm。 一个例子是循环迭代f（n）-n次的某个倍数，其中f（n）是某个函数，其值保证大于n，当n接近无限时，f（n）-n的极限是零。 对于所有的n，f（n）的计算也需要是恒定的。 我不知道f（n）看起来是什么样的，或者这样一个algorithm会有什么应用，但是在我看来，这样的函数可能存在，但是最终的algorithm除了certificatealgorithm的可能性O（1 / N）。
我不知道algorithm，但在随机algorithm中出现的复杂度小于O（1）。 实际上，o（1）（小o）小于O（1）。 这种复杂性通常出现在随机algorithm中。 例如，正如你所说的，当事件的概率是1 / n时，他们用o（1）表示。 或者当他们想要说出事情发生的概率很高时（例如1 – 1 / n），他们用1 – o（1）表示。
如果答案是相同的，不pipeinput数据如何，那么你有一个O（0）algorithm。
换句话说，答案在提交input数据之前是已知的 – 函数可以被优化 – 所以O（0）
Big-O符号表示algorithm的最坏情况 ，与典型的运行时间不同。 certificateO（1 / n）algorithm是O（1）algorithm很简单。 根据定义，
对于所有的n> = C> 0，O（1 / n）→T（n）<= 1 / n
O（1 / n）→T（n）<= 1 / C，因为对于所有的n> = C，1 /n≤1/
O（1 / n）→O（1），因为Big-O符号忽略常量（即C的值无关紧要）
Nothing is smaller than O(1) Big-O notation implies the largest order of complexity for an algorithm
If an algorithm has a runtime of n^3 + n^2 + n + 5 then it is O(n^3) The lower powers dont matter here at all because as n -> Inf, n^2 will be irrelevant compared to n^3
Likewise as n -> Inf, O(1/n) will be irrelevant compared to O(1) hence 3 + O(1/n) will be the same as O(1) thus making O(1) the smallest possible computational complexity
inline void O0Algorithm() {}
