有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
随着人口增长,哪些问题会变得更容易?一个答案是像bittorrent这样的东西,下载速度是节点数量的逆函数。与汽车加载越多速度越慢相反,像bittorrent这样的文件共享网络连接的节点越多速度就越快。
其他回答
是的。
只有一种算法运行时为O(1/n),即“空”算法。
对于O(1/n)的算法来说,这意味着它渐进地执行的步骤比由单个指令组成的算法少。如果对于所有n个> n0,它执行的步骤少于1步,则对于这n个,它必须完全不包含任何指令。由于检查' If n > n0'至少需要1条指令,因此对于所有n个,它必须不包含任何指令。
总结: 唯一的算法是O(1/n)是空算法,不包含任何指令。
我相信量子算法可以通过叠加“一次”进行多次计算……
我怀疑这是一个有用的答案。
你不能低于O(1)但是O(k) k小于N是可能的。我们称之为次线性时间算法。在某些问题中,次线性时间算法只能给出特定问题的近似解。然而,有时,一个近似解就可以了,可能是因为数据集太大了,或者计算所有数据的计算成本太高了。
我猜小于O(1)是不可能的。算法所花费的任何时间都称为O(1)。但是对于O(1/n)下面的函数呢。(我知道这个解决方案中已经出现了许多变体,但我猜它们都有一些缺陷(不是主要的,它们很好地解释了这个概念)。这里有一个,只是为了方便讨论:
def 1_by_n(n, C = 10): #n could be float. C could be any positive number
if n <= 0.0: #If input is actually 0, infinite loop.
while True:
sleep(1) #or pass
return #This line is not needed and is unreachable
delta = 0.0001
itr = delta
while delta < C/n:
itr += delta
因此,随着n的增加,函数将花费越来越少的时间。此外,如果输入实际为0,则函数将永远返回。
有人可能会说,这将受到机器精度的限制。因此,由于c eit有一个上界,它是O(1)。但我们也可以绕过它,通过在字符串中输入n和C。加法和比较是对字符串进行的。用这个方法,我们可以把n减小到任意小。因此,即使忽略n = 0,函数的上限也是无界的。
我也相信我们不能说运行时间是O(1/n)。我们应该写成O(1 + 1/n)
从我之前学习的大O符号来看,即使你需要1步(比如检查一个变量,做一个赋值),那也是O(1)。
注意,O(1)和O(6)是一样的,因为“常数”并不重要。这就是为什么O(n)和O(3n)是一样的。
如果你需要1步,那就是O(1)。因为你的程序至少需要1步,所以算法的最小值是O(1)。除非我们不这样做,那么它是O(0),对吧?如果我们做任何操作,那么它就是O(1)这是它能达到的最小值。
(如果我们选择不这样做,那么它可能成为一个禅宗或道的问题……在编程领域,O(1)仍然是最小值)。
或者这样怎么样:
程序员:老板,我找到了一个在O(1)时间内完成的方法! 老板:没必要,今天早上我们就要破产了。 程序员:哦,那么它就变成了O(0)。