是否有任何 O(1/n) 算法？
或者其他任何小于 O(1) 的东西？
问问题
67360 次
32 回答
329
这个问题并不像在某些人看来那么愚蠢。至少在理论上，当我们采用大 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的非常简单的文本搜索算法为例。在这里，预期的运行时间将随着搜索模式长度的增加而减少（但是增加干草堆的长度将再次增加运行时间）。
于 2009-05-25T08:10:15.847 回答
155
是的。
恰好有一种运行时间为 O(1/n) 的算法，即“空”算法。
算法为 O(1/n) 意味着它以比由单个指令组成的算法更少的步骤渐近执行。如果对于所有 n > n0，它执行的步骤少于一个步骤，那么对于那些 n，它必须完全不包含任何指令。由于检查“如果 n > n0”至少需要 1 条指令，因此它必须不包含所有 n 的指令。
总结： O(1/n) 的唯一算法是空算法，不包含指令。
于 2009-06-11T17:40:02.927 回答
25
sharptooth 是正确的，O(1) 是最好的性能。但是，它并不意味着快速的解决方案，只是一个固定时间的解决方案。
一个有趣的变体，也许真正被建议的是，随着人口的增长，哪些问题会变得更容易。我能想到 1，虽然是做作和半开玩笑的答案：
一组中是否有两个人的生日相同？当 n 超过 365 时，返回 true。虽然小于 365，但这是 O(n ln n)。也许不是一个很好的答案，因为问题并没有慢慢变得更容易，而是在 n > 365 时变成 O(1)。
于 2009-05-25T07:01:49.947 回答
23
那是不可能的。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 的增加而减小，估计不会改变。
于 2009-05-25T06:21:23.840 回答
17
从我之前学习的大 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)。
于 2009-05-25T06:47:38.930 回答
8
不，这是不可能的：
由于 n 在 1/n 中趋于无穷大，我们最终达到 1/(inf)，实际上是 0。
因此，问题的大哦类将是 O(0)，n 很大，但更接近常数时间，n 较低。这是不明智的，因为唯一可以比恒定时间更快地完成的事情是：
void nothing() {};
甚至这是有争议的！
一旦你执行一个命令，你至少处于 O(1)，所以不，我们不能有一个 O(1/n) 的大哦类！
于 2009-05-25T12:45:40.597 回答
7
根本不运行该功能（NOOP）怎么办？或使用固定值。这算不算？
于 2009-05-25T08:10:03.913 回答
7
我经常使用 O(1/n) 来描述随着输入变大而变小的概率——例如，公平硬币在 log2(n) 翻转时出现反面的概率是 O(1/n)。
于 2009-05-25T17:52:18.063 回答
7
对于阅读此问题并想了解对话内容的任何人，这可能会有所帮助：
| |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 |
于 2016-04-30T01:57:23.537 回答
6
O(1) 仅表示“恒定时间”。
当您向循环[1] 添加提前退出时，您（在大 O 表示法中）将 O(1) 算法转换为 O(n)，但使其更快。
诀窍通常是恒定时间算法是最好的，线性优于指数，但对于少量的 n，指数算法实际上可能更快。
1：假设此示例的静态列表长度
于 2009-05-25T12:28:45.170 回答
4
很多人都得到了正确答案（否） 这是另一种证明方式：为了拥有一个函数，您必须调用该函数，并且必须返回一个答案。这需要一定的恒定时间。即使其余的处理过程花费更少的时间来处理较大的输入，打印出答案（我们可以假设为单个位）至少需要恒定的时间。
于 2010-07-09T19:29:46.037 回答
3
我相信量子算法可以通过叠加“一次”进行多项计算......
我怀疑这是一个有用的答案。
于 2009-05-25T06:20:14.763 回答
2
如果存在解决方案，则可以在恒定时间 = 立即准备和访问它。例如，如果您知道排序查询是逆序的，则使用 LIFO 数据结构。假设选择了适当的模型 (LIFO)，则数据已经排序。
于 2009-05-25T06:32:22.403 回答
2
你不能低于 O(1)，但是在 O(k) 中 k 小于 N 是可能的。我们称它们为次线性时间算法。在某些问题中，次线性时间算法只能给出特定问题的近似解。然而，有时，一个近似的解决方案就很好，可能是因为数据集太大，或者计算量太大而无法全部计算。
于 2009-05-25T06:51:32.777 回答
2
随着人口的增长，哪些问题会变得更容易？一个答案是像 bittorrent 这样的东西，其中下载速度是节点数量的反函数。与加载越多的汽车速度越慢相反，像 bittorrent 这样的文件共享网络连接的节点越多，速度就越快。
于 2009-05-25T07:22:06.320 回答
1
O(1/n) 不小于 O(1)，这基本上意味着你拥有的数据越多，算法运行得越快。假设你得到一个数组，如果它的元素少于 10 100 个，则总是填充它，如果有更多则什么也不做。这当然不是 O(1/n) 而是像 O(-n) 之类的东西 :) 太糟糕了 O-big 符号不允许负值。
于 2009-05-25T06:32:24.307 回答
1
那这个呢：
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
随着列表大小的增加，程序的预期运行时间会减少。
于 2009-05-25T06:37:12.020 回答
1
正如已经指出的那样，除了可能的 null 函数异常之外，不可能有任何O(1/n)函数，因为所花费的时间将不得不接近 0。
O(1)当然，有一些算法，比如 Konrad 定义的算法，至少在某种意义上它们似乎应该小于。
def get_faster(list):
how_long = 1/len(list)
sleep(how_long)
如果你想研究这些算法，你应该定义你自己的渐近测量，或者你自己的时间概念。例如，在上面的算法中，我可以允许使用一定数量的“自由”操作。在上述算法中，如果我通过排除除睡眠之外的所有时间来定义 t'，则 t'=1/n，即 O(1/n)。可能有更好的例子，因为渐近行为是微不足道的。事实上，我确信外面的某个人可以想出能给出不平凡结果的感官。
于 2010-07-09T11:19:32.083 回答
1
其余大多数答案都将 big-O 解释为完全与算法的运行时间有关。但是由于问题没有提到它，我认为值得一提的是 big-O 在数值分析中的另一个应用，即关于误差。
许多算法可以是 O(h^p) 或 O(n^{-p})，具体取决于您是在谈论步长 (h) 还是划分数 (n)。例如，在欧拉方法中，假设您知道 y(0) 和 dy/dx（y 的导数），您会寻找 y(h) 的估计值。h 越接近 0，您对 y(h) 的估计就越准确。因此，为了找到某个任意 x 的 y(x)，需要将区间 0 到 x，将其拆分为 n 块，然后运行欧拉方法在每个点，从 y(0) 到 y(x/n) 到 y(2x/n)，依此类推。
因此，欧拉的方法是 O(h) 或 O(1/n) 算法，其中 h 通常被解释为步长，n 被解释为划分区间的次数。
由于浮点舍入误差，您还可以在实际数值分析应用程序中使用 O(1/h) 。间隔越小，某些算法的实现发生的取消越多，有效数字的丢失越多，因此错误越多，这些错误会通过算法传播。
对于欧拉方法，如果您使用浮点数，请使用足够小的步长并取消，并且您将小数添加到大数中，而大数保持不变。对于通过从在两个非常接近的位置评估的函数中减去彼此的两个数字来计算导数的算法，在平滑函数 y 中用 (y(x+h) - y(x) / h) 逼近 y'(x) (x+h) 接近 y(x) 导致较大的抵消和对具有较少有效数字的导数的估计。这将反过来传播到您需要导数的任何算法（例如，边界值问题）。
于 2017-07-30T02:07:18.087 回答
1
我想少于 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，那么函数将永远返回。
有人可能会争辩说，它将受到机器精度的限制。因此，因为 eit 有一个上限，它是 O(1)。但是我们也可以通过在字符串中输入 n 和 C 来绕过它。加法和比较是在字符串上完成的。想法是，有了这个，我们可以将 n 减少到任意小。因此，即使我们忽略 n = 0，函数的上限也是无界的。
我也相信我们不能只说运行时间是 O(1/n)。但我们应该说像 O(1 + 1/n)
于 2019-01-27T01:21:06.370 回答
0
好的，我想了想，也许有一个算法可以遵循这个一般形式：
您需要计算 1000 个节点图的旅行商问题，但是，您还会得到一个无法访问的节点列表。随着不可访问节点的列表越来越大，问题变得更容易解决。
于 2009-05-25T06:32:12.340 回答
0
我看到一个算法的上限是 O(1/n)：
由于例程外部的某些原因，您有大量输入正在发生变化（可能它们反映了硬件，或者甚至可能是处理器中的其他内核执行此操作。）并且您必须选择一个随机但有效的输入。
现在，如果它没有改变，您只需制作一个项目列表，随机选择一个并获得 O(1) 时间。但是，数据的动态特性无法列出列表，您只需随机探测并测试探测的有效性。（请注意，本质上，不能保证返回时答案仍然有效。这仍然可以使用 - 例如，游戏中的一个单位的 AI。它可以射击一个在视线范围内消失的目标扣动扳机。）
这具有无穷大的最坏情况性能，但平均情况性能会随着数据空间的填满而下降。
于 2009-05-28T00:36:35.470 回答
0
在数值分析中，逼近算法的逼近容差应该具有亚常数渐近复杂度。
class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}
于 2010-01-24T00:12:54.050 回答
-1
有可能构造一个 O(1/n) 的算法。一个例子是一个循环，它迭代 f(n)-n 的某个倍数，其中 f(n) 是某个函数，其值保证大于 n，并且当 n 接近无穷大时 f(n)-n 的极限是零。对于所有 n，f(n) 的计算也需要保持不变。我不知道 f(n) 会是什么样子，也不知道这样的算法会有什么应用，但在我看来，这样的函数可能存在，但生成的算法除了证明算法的可能性之外没有其他目的O(1/n)。
于 2011-04-29T23:08:34.047 回答
-2
如果无论输入数据如何，答案都是相同的，那么您就有一个 O(0) 算法。
或者换句话说 - 在提交输入数据之前答案是已知的 - 可以优化函数 - 所以 O(0)
于 2009-05-25T08:15:13.043 回答
-2
Big-O 表示法表示算法的最坏情况，这与其典型的运行时间不同。证明 O(1/n) 算法是 O(1) 算法很简单。根据定义，
O(1/n) --> T(n) <= 1/n，对于所有 n >= C > 0
O(1/n) --> T(n) <= 1/C，因为1/n <= 1/C for all n >=C
O(1/n) --> O(1)，因为 Big-O 表示法忽略了常量（即 C 的值无关紧要）
于 2009-05-25T13:18:41.777 回答
-2
没有什么小于 O(1) Big-O 表示法意味着算法的最大复杂度顺序
如果算法的运行时间为 n^3 + n^2 + n + 5，那么它是 O(n^3) 较低的幂在这里根本不重要，因为当 n -> Inf 时，n^2 与n^3
同样作为 n -> Inf，与 O(1) 相比，O(1/n) 将无关紧要，因此 3 + O(1/n) 将与 O(1) 相同，从而使 O(1) 成为可能的最小计算量复杂
于 2009-05-28T00:08:51.877 回答
-2
inline void O0Algorithm() {}
于 2009-08-17T09:50:06.637 回答
-2
这是一个简单的 O(1/n) 算法。它甚至做了一些有趣的事情！
function foo(list input) {
int m;
double output;
m = (1/ input.size) * max_value;
output = 0;
for (int i = 0; i < m; i++)
output+= random(0,1);
return output;
}
O(1/n) 是可能的，因为它描述了随着输入大小的增加，函数的输出如何变化。如果我们使用函数 1/n 来描述函数执行的指令数，那么对于任何输入大小，函数都不需要零指令。相反，对于每个输入大小，n 高于某个阈值，所需的指令数以正常数乘以 1/n 为界。由于没有 1/n 为 0 的实际数字，并且常数为正，因此没有理由将函数限制为采用 0 或更少的指令。
于 2009-09-15T22:43:43.433 回答
-2
我不了解算法，但小于 O(1) 的复杂性出现在随机算法中。实际上，o(1)（小 o）小于 O(1)。这种复杂性通常出现在随机算法中。例如，正如您所说，当某些事件的概率为 1/n 时，它们用 o(1) 表示。或者当他们想说某事发生的概率很高（例如 1 - 1/n）时，他们用 1 - o(1) 来表示它。
于 2016-04-24T19:15:15.400 回答
-3
我不懂数学，但这个概念似乎是在寻找一个随着你添加更多输入而花费更少时间的函数？在这种情况下怎么办：
def f( *args ):
if len(args)<1:
args[1] = 10
添加可选的第二个参数时，此函数更快，因为否则必须分配它。我意识到这不是一个等式，但维基百科页面说 big-O 也经常应用于计算系统。
于 2009-05-25T08:24:35.180 回答
-3
有亚线性算法。事实上，Bayer-Moore 搜索算法就是一个很好的例子。
于 2010-01-24T00:23:30.420 回答