有没有O(1/n)种算法?
或者其他小于O(1)的数?
有没有O(1/n)种算法?
或者其他小于O(1)的数?
当前回答
如果不管输入数据如何,答案都是一样的,那么你就有一个O(0)算法。
或者换句话说——在提交输入数据之前,答案就已经知道了 -这个功能可以优化-所以O(0)
其他回答
正如已经指出的,除了null函数可能的例外,不可能有O(1/n)个函数,因为所花费的时间必须接近0。
当然,有一些算法,比如康拉德定义的算法,它们至少在某种意义上应该小于O(1)
def get_faster(list):
how_long = 1/len(list)
sleep(how_long)
If you want to investigate these algorithms, you should either define your own asymptotic measurement, or your own notion of time. For example, in the above algorithm, I could allow the use of a number of "free" operations a set amount of times. In the above algorithm, if I define t' by excluding the time for everything but the sleep, then t'=1/n, which is O(1/n). There are probably better examples, as the asymptotic behavior is trivial. In fact, I am sure that someone out there can come up with senses that give non-trivial results.
好吧,我想了一下,也许有一个算法可以遵循这个一般形式:
你需要计算一个1000节点图的旅行商问题,但是,你也有一个你不能访问的节点列表。随着不可访问节点列表的增加,问题变得更容易解决。
O(1/n)并不小于O(1)这基本上意味着你拥有的数据越多,算法运行得越快。假设你有一个数组,如果它小于10100个元素就填充它,如果多于10100个元素就什么都不做。这个当然不是O(1/n),而是O(-n):)太糟糕了,O大符号不允许负数。
没有比O(1)小的数 大o符号表示算法的最大复杂度
如果一个算法的运行时间是n³+ n²+ n + 5那么它就是O(n³) 低次在这里根本不重要,因为n ->正无穷,n^2与n^3相比是无关的
同样地,当n -> Inf时,O(1/n)与O(1)相比是不相关的,因此3 + O(1/n)将与O(1)相同,从而使O(1)的计算复杂度最小
大o符号表示算法与典型运行时不同的最坏情况。证明O(1/n)算法是O(1)算法很简单。根据定义, O(1/n)——> T(n) <= 1/n, for all n >= C > 0 O (1 / n)——> T (n) < = 1 / C,因为1 / n <所有n > = 1 / C = C O(1/n)——> O(1),因为大O符号忽略常数(即C的值无关紧要)