首页 文章

有没有O（1 / n）算法？

提问于
浏览 次
321

有没有O（1 / n）算法？

或者其他任何小于O（1）的东西？

theory complexity-theory big-o

30 回答

  • -2

    这个问题并不像看起来那么愚蠢 . 至少在理论上，当我们采用Big O notation的数学定义时，诸如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采用非常简单的文本搜索算法 . 这里，随着搜索模式的长度增加，预期的运行时间将减少（但是，草堆的长度将再次增加运行时间） .

    回复于
  • 0

    是 .

    只有一种算法具有运行时O（1 / n），即“空”算法 .

    对于算法为O（1 / n）意味着它以比由单个指令组成的算法更少的步骤渐近地执行 . 如果它对所有n> n0执行的步骤少于一步，那么对于那些n，它必须完全没有指令 . 由于检查'if n> n0'至少花费1条指令，因此它必须不包含所有n的指令 .

    总结：唯一的算法是O（1 / n）是空算法，由无指令组成 .

    回复于
  • 1

    那是不可能的 . 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增加而减小，则估计不会改变 .

    回复于
  • 3

    sharptooth是正确的，O（1）是最好的表现 . 但是，它并不意味着快速解决方案，只是一个固定的时间解决方案 .

    一个有趣的变体，也许真正建议的是，随着人口的增长，哪些问题变得更容易 . 我可以想到1，虽然是做作和诙谐的回答：

    一组中的任何两个人都有同一个生日？当n超过365时，返回true . 虽然小于365，但这是O（n ln n） . 也许不是一个很好的答案，因为问题不会慢慢变得容易，但只要在n> 365时变为O（1） .

    回复于
  • -1

    从我之前学习的大O符号开始，即使你需要1步（比如检查一个变量，做一个赋值），那就是O（1） .

    注意，O（1）与O（6）相同，因为“常数”无关紧要 . 这就是我们说O（n）与O（3n）相同的原因 .

    因此，如果您甚至需要一步，那就是O（1）......并且因为您的程序至少需要1步，所以算法的最小值可以是O（1） . 除非我们不这样做，否则它是O（0），我想？如果我们做任何事情，那么它是O（1），这是它可以达到的最小值 .

    （如果我们选择不这样做，那么它可能成为一个禅或道问题......在编程领域，O（1）仍然是最小的） .

    或者这个怎么样：

    programmer ：老板，我找到了办法在O（1）时间做到这一点！
    boss ：没必要，我们今天早上破产了 .
    programmer ：哦，那就变成了O（0） .

    回复于
  • -1

    不，这是不可能的：

    由于n在1 / n中倾向于无穷大，我们最终实现1 /（inf），实际上是0 .

    因此，问题的大哦类别是具有大量n的O（0），但是具有低n的接近恒定时间 . 这是不明智的，因为唯一可以在比常数更快的时间内完成的事情是：

    void nothing() {};

    甚至这是有争议的！

    一旦你执行一个命令，你至少在O（1），所以不，我们不能有一个很大的O级（1 / n）！

    回复于
  • 5

    怎么没有运行该功能（NOOP）？或使用固定值 . 这算数了吗？

    回复于
  • 1

    我经常使用O（1 / n）来描述随着输入变大而变小的概率 - 例如，在log2（n）翻转时公平硬币出现的概率是O（1 / n） .

    回复于
  • 0

    O（1）仅表示“恒定时间” .

    当您添加提前退出时循环[1]你是（用大O表示法）将O（1）算法转换为O（n），但使其更快 .

    诀窍通常是恒定时间算法是最好的，线性比指数更好，但对于少量的n，指数算法实际上可能更快 .

    1：假设此示例的静态列表长度

    回复于
  • -1

    我相信量子算法可以通过叠加“一次”进行多次计算......

    我怀疑这是一个有用的答案 .

    回复于
  • 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 |
    回复于
  • 25

    很多人都有正确的答案（不）这是证明它的另一种方式：为了拥有一个功能，你必须调用该功能，你必须返回一个答案 . 这需要一定的时间 . 即使其余的处理花费更少的时间来处理更大的输入，打印答案（我们可以假设是一个单位）至少需要一个恒定的时间 .

    回复于
  • 0

    如果存在解决方案，则可以在恒定时间内立即准备和访问它 . 例如，如果您知道排序查询是针对逆序，则使用LIFO数据结构 . 然后，在选择了适当的模型（LIFO）的情况下，数据已经被排序 .

    回复于
  • 2

    随着人口增长，哪些问题变得更容易一个答案是像bittorrent这样的东西，其中下载速度是节点数量的反函数 . 与汽车相反，汽车越慢，加载越多，像bittorrent这样的文件共享网络会加速连接的节点越多 .

    回复于
  • 1

    你不能低于O（1），但是k（小于N）的O（k）是可能的 . 我们称他们为sublinear time algorithms . 在一些问题中，次线性时间算法只能给出特定问题的近似解 . 然而，有时，近似解决方案很好，可能是因为数据集太大，或者计算所有数据的计算成本太高 .

    回复于
  • 0

    O（1 / n）不小于O（1），它基本上意味着你拥有的数据越多，算法就越快 . 假设你得到一个数组并且总是填充最多10100个元素，如果它少于那个并且如果有更多则什么也不做 . 这个当然不是O（1 / n）但是类似于O（-n）:)太糟糕的O-big表示法不允许负值 .

    回复于
  • 15

    正如已经指出的那样，除了null函数可能的例外之外，不能有 O(1/n) 函数，因为所花费的时间必须接近0 .

    当然，有一些算法，比如Konrad定义的算法，看起来它们至少在某种程度上应该小于 O(1) .

    def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

    如果您想研究这些算法，您应该定义自己的渐近测量，或者您自己的时间概念 . 例如，在上述算法中，我可以允许使用一定次数的“自由”操作 . 在上面的算法中，如果我通过排除除睡眠之外的所有时间来定义t'，那么t'= 1 / n，即O（1 / n） . 可能有更好的例子，因为渐近行为是微不足道的 . 事实上，我确信那里的某个人可以想出能给出非平凡结果的感官 .

    回复于
  • 2

    其余大部分答案都将big-O解释为完全与算法的运行时间有关 . 但由于这个问题没有提到它，我认为值得一提的是big-O在数值分析中的其他应用，即关于错误 .

    许多算法可以是O（h ^ p）或O（n ^ { - p}），这取决于你是在谈论步长（h）还是分数（n） . 例如，在Euler's method中，如果您知道y（0）和dy / dx（y的导数），则会查找y（h）的估计值 . 你的y（h）的估计值越准确越接近h为0.因此，为了找到某个任意x的y（x），需要将间隔0到x，将其分解为n个，然后运行Euler方法在每个点，从y（0）到y（x / n）到y（2x / n），依此类推 .

    因此，Euler的方法是O（h）或O（1 / n）算法，其中h通常被解释为步长，n被解释为划分区间的次数 .

    由于floating point rounding errors，您还可以在实际数值分析应用中使用O（1 / h） . 您创建间隔越小，某些算法的实现取消的次数就越多，有效数字的丢失就越多，因此会产生更多错误，这些错误会通过算法传播 .

    对于Euler方法，如果使用浮点数，请使用足够小的浮点数步骤和取消，你将一个小数字添加到一个大数字，保持大数字不变 . 对于通过从两个非常接近的位置处评估的函数中相互减去两个数来计算导数的算法，在平滑函数y（xh）中近似y'（x）和（y（xh） - y（x）/ h） ）接近y（x）导致大的取消和对具有较少有效数字的导数的估计 . 这将依次传播到您需要导数的任何算法（例如，边界值问题） .

    回复于
  • 23

    好吧，我做了一些思考，也许存在一个可以遵循这种一般形式的算法：

    您需要计算1000个节点图的旅行商问题，但是，您还会获得一个您无法访问的节点列表 . 随着不可访问节点列表变大，问题变得更容易解决 .

    回复于
  • 2

    那这个呢：

    void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

    随着列表大小的增加，程序的预期运行时间会减少 .

    回复于
  • 7

    我看到一个O（1 / n）的算法无可置疑地在上限：

    你有一大堆输入因为例程外部的东西而改变（可能它们反映了硬件，甚至可能是处理器中的其他核心） . 你必须选择一个随机但有效的输入 .

    现在，如果它没有改变，你只需要制作一个项目列表，随机选择一个并获得O（1）时间 . 但是，数据的动态特性排除了列表，您只需随机探测并测试探针的有效性 . （并且注意到固有地不能保证答案在返回时仍然有效 . 这仍然可以用于 - 例如，游戏中的一个单位的AI . 它可以射击在视线之外掉落的目标扣动扳机 . ）

    这具有无穷大的最差情况，但随着数据空间的填满，平均情况下的性能下降 .

    回复于
  • 298

    在数值分析中，近似算法在近似容差中应具有亚常数渐近复杂度 .

    class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}
    回复于
  • -2

    我想小于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，则该函数将永远返回 .

    有人可能会说，它将受到机器精度的限制 . 因此sinc eit有一个上界，它是O（1） . 但我们也可以通过在字符串中输入n和C来绕过它 . 并且对字符串进行添加和比较 . 想法是，有了这个我们可以减少n任意小 . 因此，即使忽略n = 0，函数的上限也不受限制 .

    我也相信我们不能只说跑步时间是O（1 / n） . 但我们应该说像O（1 1 / n）

    回复于
  • 6

    我在2007年遇到了这样的疑问，很高兴看到这个帖子，我从我的reddit线程来到这个帖子 - > http://www.reddit.com/r/programming/comments/d4i8t/trying_to_find_an_algorithm_with_its_complexity/

    回复于
  • 8

    可以构造一个O（1 / n）的算法 . 一个例子是循环迭代f（n）-n次的一些倍数，其中f（n）是一些函数，其值保证大于n，并且当n接近无穷大时f（n）-n的极限是零 . 对于所有n，f（n）的计算也需要是常数 . 我不知道f（n）看起来会是什么样的或者这样的算法会有什么应用，但是在我看来这样的函数可能存在，但是得到的算法没有其他目的，只能证明算法的可能性 . O（1 / N） .

    回复于
  • -2

    我不知道算法，但在随机算法中出现的复杂度小于O（1） . 实际上，o（1）（小o）小于O（1） . 这种复杂性通常出现在随机算法中 . 例如，正如您所说，当某个事件的概率为1 / n时，它们用o（1）表示 . 或者当他们想要说某些事情发生的概率很高（例如1 - 1 / n）时，他们用1 - o（1）表示它 .

    回复于
  • 7

    如果答案是相同的，无论输入数据如何，那么您有一个O（0）算法 .

    换句话说 - 在提交输入数据之前知道答案 - 可以优化函数 - 所以O（0）

    回复于
  • -2

    Big-O表示法表示算法的 worst case scenario ，它与其典型的运行时间不同 . 很容易证明O（1 / n）算法是O（1）算法 . 根据定义，
    O（1 / n） - > T（n）<= 1 / n，对于所有n> = C> 0
    O（1 / n） - > T（n）<= 1 / C，因为对于所有n> = C，1 / n <= 1 / C
    O（1 / n） - > O（1），因为Big-O表示法忽略常量（即C的值无关紧要）

    回复于
  • 0

    没有什么比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）成为可能的最小计算复杂度

    回复于
  • 128
    inline void O0Algorithm() {}
    回复于

相关问题