Kon*_*lph 308
这个问题并不像看起来那么愚蠢.至少在理论上,当我们采用Big O符号的数学定义时,诸如O(1/n)之类的东西是完全合理的:
现在你可以很容易地用g(x)代替1/x ......显然上面的定义仍然适用于某些f.
为了估计渐近运行时增长,这是不太可行的......随着输入的增长,有意义的算法不能更快.当然,您可以构建一个任意算法来实现这一点,例如:
def get_faster(list):
how_long = (1 / len(list)) * 100000
sleep(how_long)
显然,这个函数在输入大小增加时花费的时间更少......至少在某些限制之前,由硬件强制执行(数字的精确度,sleep可以等待的最短时间,处理参数的时间等):这个限制将是一个因此,上面的函数仍然具有运行时O(1).
但是,是实际上真实世界的算法在运行时可以减少(至少部分地)输入大小增加时.请注意,这些算法不会表现出低于O(1)的运行时行为.他们仍然很有趣.例如,采用Horspool的非常简单的文本搜索算法.这里,随着搜索模式的长度增加,预期的运行时间将减少(但是,草堆的长度将再次增加运行时间).
- 你必须喜欢任何开头的答案"这个问题并不像看起来那么愚蠢." (43认同)
- Mehrdad,你不明白.O符号是关于*limit*(技术上为sup sup)的n - >∞.算法/程序的运行时间是某台机器上的步数,因此是离散的 - 算法可以采用的时间非零下限("一步").它**可能是高达*某些有限N*一个程序需要用n减少许多步骤,但算法可以是O(1/n),或者实际上是o(1)的唯一方法是,如果它需要时间0表示所有足够大的n - 这是不可能的. (27认同)
- 我们并不反对存在O(1/n)*函数*(在数学意义上).显然他们这样做.但计算本质上是离散的.具有下限的东西,例如程序的运行时间 - 在冯·诺伊曼体系结构或纯粹抽象的图灵机上 - *不能是O(1/n).等价地,O(1/n)的东西不能有下限.(必须调用你的"睡眠"功能,或者必须检查变量"list" - 或者必须在图灵机上检查输入磁带.所以所用的时间会随着n的变化而变化ε+ 1/n,不是O(1/n)) (27认同)
- "由硬件强制执行"也适用于图灵机.在O(1/n)的情况下,总是存在输入大小,算法不应该执行任何操作.因此,我认为O(1/n)时间复杂度确实无法实现. (22认同)
- 如果T(0)=∞,它不会停止.没有"T(0)=∞,但它仍然停止".此外,即使你在R∪{∞}中工作并定义T(0)=∞,并且T(n + 1)= T(n)/ 2,所以对于所有n,T(n)=∞.让我再说一遍:如果离散值函数是O(1/n),那么对于所有足够大的n,它就是0. [证明:T(n)= O(1/n)意味着存在一个常数c,使得对于n> N0,T(n)<c(1/n),这意味着对于任何n> max(N0,1/c),T(n)<1,这意味着T(n)= 0.没有机器,真实的或抽象的,可以花费0时间:它*有*来查看输入.好吧,除了从不做任何事情的机器,并且对于所有n,T(n)= 0. (15认同)
- ShreevatsaR:你的离散化一切都很好但是因为我们在这里谈论理论,所以我只是继续并定义我的例子中的`sleep`函数没有离散的步长,所以那里!请不要通过混合理论概念和现实来使这个讨论更加混乱.所有人都同意:实际上,没有O(1/n)运行时.满意？(但是,实际上,由于Von Neumann架构的限制,所有算法都是O(1).这使我们绝对无处可去.) (6认同)
- 即使在量子计算机中,(可测量的)变化也只是离散地发生.在任何情况下,离散性实际上并不重要:初始步骤(检查输入)需要一些时间(比如ε),所以即使我们忽略"睡眠"时间,我们对所有n都有T(n)≥ε,而另一方面,如果T(n)= O(1/n),我们将得到T(n) - > 0作为n - >∞. (4认同)
- @Mehrdad:我不是在谈论O符号(这只是描述了一组函数,没有任何时间连接),但*算法*的概念通常是在图灵机上定义的.TM以不连续的步骤进行.在谈论算法的时间复杂度时,您实际上正在讨论等效TM必须采用的*步数*的增长函数.这就是我怀疑存在O(1/n)算法(= TM)的原因. (3认同)
- @__roland__:不是这样.O符号与算法所采用的步骤无关,但时间函数的*增长*作为输入的函数.O符号的逐步隐喻是我们正在努力实现有限的机器的一个不幸后果(正如我在回答中所描述的那样).这不是O的真正含义. (2认同)
- @Mehrdad:你是对的,绝对数字被定义中的常量抽象掉了.但是对于O(1/n),绝对步数根本不重要:因为1/n接近零,我总是可以选择足够大的n来让任何(离散的!)步数为零,无论如何使用了什么常量. (2认同)
- @Mehrdad:"f(n)= O(g(n))"表示当n高于某个"阈值"值N0时,f(n)必须<= M*g(n).要理解的主要是尽管你可以自由选择常数N0和M,但你必须事先选择它们** - 它们不允许是n的函数.并且,对于你做出的任何*N0和M的选择,任何采取1步或更多步的算法最终都会超过M*(1/n)(即有一些输入大小为k,使得k> N0和f(k) )> M*(1/k)). (2认同)
Tob*_*ias 134
是.
只有一种算法具有运行时O(1/n),即"空"算法.
对于算法为O(1/n)意味着它以比由单个指令组成的算法更少的步骤渐近地执行.如果它对所有n> n0执行的步骤少于一步,那么对于那些n,它必须完全没有指令.由于检查'if n> n0'至少花费1条指令,因此它必须不包含所有n的指令.
总结:唯一的算法是O(1/n)是空算法,由无指令组成.
- 任何O(0)函数也是O(1/n),也是O(n),也是O(n ^ 2),也是O(2 ^ n).叹了口气,没有人理解简单的定义吗？O()是一个上限. (30认同)
- 这是这个帖子中唯一正确的答案,并且(尽管我的upvote)它是零票.这就是StackOverflow,其中"正确的"答案被投票高于实际正确的答案. (23认同)
- @ kenj0418你在每一句话都设法错了."当N独立于N时,表示与N相关的大哦值是不正确的." 常数函数是一个完美的goof函数."其次,运行任何程序,即使是刚存在的程序,至少需要一段时间,O(1)." 复杂性的定义并没有说明实际运行任何程序."它是O(0),而不是O(1/n)".请参阅@ ShreevatsaR的评论. (13认同)
- 不,它的评级为0,因为它不正确.当N独立于N时,表示与N相关的大哦值是不正确的.其次,运行任何程序,即使是刚存在的程序,至少需要一段时间,O(1).即使不是这种情况,它也是O(0),而不是O(1/n). (4认同)
- 所以如果有人问空算法的时间复杂度是多少，你会回答 O(1/n) ??? 不知怎的，我对此表示怀疑。 (3认同)
- 看来你不是水管工.好答案. (2认同)
sha*_*oth 24
那是不可能的.Big-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增加而减小,则估计不会改变.
- 我怀疑这个答案是"正确的",但不幸的是我缺乏理解它的智慧. (41认同)
- 我不明白定义(甚至更正)如何与OP的问题相矛盾.该定义适用于完全随意的功能!1/n对于B来说是一个完全合理的函数,实际上你的方程并不与此相反(只是做数学运算).所以不,尽管有很多共识,这个答案实际上是错误的*.抱歉. (28认同)
- AFAIK这个条件不一定适用于所有n,但是对于所有n> n_0(即,仅当输入的大小达到特定阈值时). (12认同)
- 错误!我不喜欢downvoting但是你说当没有明确的共识时这是不可能的.在实践中,你是正确的,如果你构造一个运行时间为1/n的函数(简单),它最终会达到一些最小时间,有效地使它在实现时成为O(1)算法.然而,没有什么能阻止算法在纸上成为O(1/n). (10认同)
- @Jason:是的,现在你说出来了...... :) @jheriko:O(1/n)的时间复杂度在纸恕我直言上不起作用.我们描述了图灵机的增长函数f(输入大小)= #ops.如果它在x步之后停止输入长度为n = 1的输入,那么我将选择一个输入大小n >> x,即足够大,如果算法确实在O(1/n)中,则不应该进行任何操作完成.图灵机应该如何注意到这一点(不允许从磁带读取一次)？ (3认同)
- @Konrad,jherico:这是一个证明(或只是重述):如果算法是O(1/n),则意味着存在常数C,使得对于所有(足够大)n,所花费的时间是T(n) )<C*(1/n).现在取任何n> 1/C. 你需要T(n)<1,即T(n)= 0,这是不可能的. (2认同)
Adr*_*ian 23
sharptooth是正确的,O(1)是最好的表现.但是,它并不意味着快速解决方案,只是一个固定的时间解决方案.
一个有趣的变体,也许真正建议的是,随着人口的增长,哪些问题变得更容易.我可以想到1,虽然是做作和诙谐的回答:
一组中的任何两个人都有同一个生日？当n超过365时,返回true.虽然小于365,但这是O(n ln n).也许不是一个很好的答案,因为问题不会慢慢变得容易,但只要在n> 365时变为O(1).
- +1.当n增加时,存在许多NP完全问题经历"相变",即当你超过n的某个阈值时它们很快变得更容易或更难.一个例子是数字分区问题:给定一组n个非负整数,将它们分成两部分,使每个部分的总和相等.在n的某个阈值处,这变得非常容易. (9认同)
- 366.别忘了闰年! (7认同)
- 你是对的。像计算机一样，我偶尔会遇到舍入错误:-) (2认同)
nop*_*ole 15
从我之前学习的大O符号开始,即使你需要1步(比如检查一个变量,做一个赋值),那就是O(1).
注意,O(1)与O(6)相同,因为"常数"无关紧要.这就是我们说O(n)与O(3n)相同的原因.
因此,如果您甚至需要一步,那就是O(1)......并且因为您的程序至少需要1步,所以算法的最小值可以是O(1).除非我们不这样做,否则它是O(0),我想？如果我们做任何事情,那么它是O(1),这是它可以达到的最小值.
(如果我们选择不这样做,那么它可能成为一个禅或道问题......在编程领域,O(1)仍然是最小的).
或者这个怎么样:
程序员:老板,我在O(1)时间找到了办法!
老板:没必要,我们今天早上破产了.
程序员:哦,那么,它变成O(0).
不,这是不可能的:
由于n在1/n中倾向于无穷大,我们最终实现1 /(inf),实际上是0.
因此,问题的大哦类别是具有大量n的O(0),但是具有低n的接近恒定时间.这是不明智的,因为唯一可以在比常数更快的时间内完成的事情是:
void nothing() {};
甚至这是有争议的!
只要你执行一个命令,你至少在O(1),所以不,我们不能有一个大哦级O(1/N)的!
怎么没有运行该功能(NOOP)？或使用固定值.这算数了吗？
- 那仍然是O(1)运行时. (16认同)
- ShreevatsaR:绝对没有矛盾.你似乎没有意识到大的O符号与函数中花费的时间*没有关系 - 相反,它描述了时间*如何随着输入的变化而改变*(高于某个值).请参阅其他评论帖子了解更多 (4认同)
- 对,那还是O(1).我不知道有人能理解这一点,但在另一个答案中声称可能比NO-OP更少. (2认同)
我经常使用O(1/n)来描述随着输入变大而变小的概率 - 例如,在log2(n)翻转时公平硬币出现的概率是O(1/n).
- 它不是重新定义,它正是大O的定义. (11认同)
- 我是一名理论计算机科学家.它是关于函数的渐近阶. (10认同)
- 那不是大O的事.你不能只是重新定义它来回答这个问题. (6认同)
- @Dave:问题不在于是否存在O(1/n)函数,这显然确实存在.相反,它是否存在O(1/n)算法,其中(可能除了null函数之外)不存在 (5认同)
- Big O是任意实函数的属性.时间复杂性只是其可能的应用之一.空间复杂度(算法使用的工作内存量)是另一个.问题是关于O(1/n)_algorithms_意味着它是其中之一(除非另一个适用于我不知道的算法).其他应用包括人口增长的订单,例如Conway的生活.另见http://en.wikipedia.org/wiki/Big_O_notation (4认同)
- 大O是时间复杂性,而不是概率. (2认同)
小智 6
O(1)仅表示"恒定时间".
当您将一个早期退出添加到循环[1]时,您(以大O表示法)将O(1)算法转换为O(n),但使其更快.
诀窍通常是恒定时间算法是最好的,线性比指数更好,但对于少量的n,指数算法实际上可能更快.
1:假设此示例的静态列表长度
我相信量子算法可以通过叠加"一次"进行多次计算......
我怀疑这是一个有用的答案.
- 这将是一个超级位置. (7认同)
- 但如果问题是淡啤酒怎么办？(啊.哈.哈.) (2认同)
- 量子算法可以进行多次计算，但只能检索一次计算的结果，不能选择得到哪个结果。值得庆幸的是，您还可以对整个量子寄存器（例如 QFT）进行操作，因此您更有可能找到一些东西:) (2认同)
- 它可能没有用,但它具有真实的优势,这使得它高于一些更高度投票的答案B-) (2认同)
小智 5
对于那些阅读此问题并希望了解对话内容的人来说,这可能有所帮助:
| |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 |