标签: asymptotic-complexity

我对能够推理其自身时间复杂度的编程语言感兴趣。为此，以某种方式以编程方式表示时间复杂度将非常有用，这将允许我执行以下操作：

f_time = O(n)
g_time = O(n^2)
h_time = O(sqrt(n))

fastest_asymptotically = min(f_time, g_time, h_time)  # = h_time
total_time = f_time.inside(g_time).followed_by(h_time)  # = O(n^3)

我目前正在使用 Python，但我并没有特别依赖于某种语言。我尝试过sympy，但我无法找到我需要的开箱即用的东西。

有没有提供这种功能的库？如果没有，是否有一种简单的方法可以使用符号数学库来执行上述操作？

编辑：我按照@Patrick87的建议编写了一个简单的库，它似乎有效。不过，我仍然对是否有其他解决方案感兴趣。

考虑排序n x n矩阵的问题(即行和列按升序排列).我想找到这个问题的下限和上限.

我发现它O(n^2 log n)只是对元素进行排序,然后将第一个n元素输出为第一行,将下一个n元素输出为第二行,依此类推.但是我想要证明它也是Omega(n^2 log n).

在尝试较小的示例之后,我想我应该证明,如果我能够使用少于n^2 log(n/e)比较来解决这个问题,那么它将违反log(m!)排序m元素所需的比较的下限.

关于如何证明这一点的任何想法？

我正在计算这个算法的运行时间？

                              Cost      No Of Times

for(j=1;j<=n-1;j++){          c1       n(loop will run for n-1 times +1 for failed cond              

    for(i=0;i<=n-2;i++){      c2       n*(n-1) (n-1 from outer loop and n for inner 

        if(a[i]>a[i+1]){      c3       (n-1)*(n-1)

            Swap              c4       (n-1)*(n-1) {in worst case }
        }
    }

在最坏的情况下, T(n)= c1*n + c2*(n-1)n + c3(n-1)(n-1)+ c4*(n-1)(n-1) 即O(n ^ 2)

在最好的情况下:

T(n)= c1*n + c2*(n-1)n + c3(n-1)(n-1) ,其为O(n ^ 2).

但实际上在最佳情况下,冒泡排序具有时间复杂度O(n). 谁能解释一下？

总和的O(1)+O(2)+ .... +O(n)评估结果是什么？

我在某处看到过它的解决方案：

O(n(n+1) / 2) = O(n^2)\n

但我对它不满意，因为O(1) = O(2) = constant，所以根据我的说法，它必须评估为O(n)only。我在科门也看到了这一点：

\xce\xa3(i=1 to n) O(i)\n

在上面的表达式中只有一个匿名函数。O(1) + O(2) + ... + O(n)这个函数与没有真正有清晰解释的函数不同 。

我试图找出 Java 中 HashMap 和 TreeMap 中 equals() 的计算复杂度。现在，您可能会说它在两种情况下都应该相同，因为 HashMap 和 TreeMap 都从 AbstractMap 继承了相同的实现。但是，在我完全接受之前，我需要一些解释。

这就是让我困惑的地方。AbstractMap 文档中覆盖的 equals() 的部分解释是：

更正式地说，如果 m1.entrySet().equals(m2.entrySet())，则两个映射 m1 和 m2 表示相同的映射。

文档不清楚 entrySet 返回的集合是 HashSet 还是 SortedSet 或其他东西。在我看来，了解这一点很重要，因为它会影响整体分析。

如果 entrySet() 返回的集合是 HashSet 类型，那么两个集合可以在 O(n) 中进行比较[在两个散列集合的情况下相等的成本]。但是，如果它们是 SortedSet 类型，那么它们可以在 O(nlogn) 中进行比较 [在两个排序集的情况下相等的成本]。因此，在 HashMap 的情况下 equals() 的复杂性在 SortedMap 的情况下会有所不同，或者至少它应该基于我的推理。

我强烈怀疑我的推理中的某个地方是错误的，所以请随时告诉我我错在哪里。什么是正确的推理。而且，最后我对 HashMap 和 SortedMap 的 equals() 的复杂性感兴趣。谢谢。

如果我正在计算字符串中字符的出现次数,我可以使用命令式语言中的数组轻松实现此操作,如下所示:

char values[256]; char c;

while (c = readChar()) {
  values[c] += 1;
}

我可以在Haskell中看到如何使用类似的东西来实现这一点Data.Vector.Mutable,它可以快速实现int-indexed可变数组.

但是,如果只使用Haskell而没有额外的包和/或扩展,我怎么能轻松地做到这一点？换句话说,我如何实现具有索引和可变性的快速O(1)集合？

Rendezvous哈希(最高随机权重"HRW")的维基百科页面提出以下声明:

虽然可能首先看起来HRW算法在O(n)时间内运行,但事实并非如此.这些站点可以按层次结构进行组织,并且HRW在每个级别应用为层次结构,从而导致O(log n)运行时间,如.[7]

我得到了参考文献的副本,"用于移动Ad-hoc网络中可扩展位置服务的基于哈希的虚拟层次结构".但是,他们的论文中引用的层次结构似乎非常特定于其应用程序域.据我所知,没有明确说明如何推广该方法.维基百科的评论使得日志似乎是一般情况.

我看了几个一般的HRW实现,但它们似乎都没有比线性时间更好的支持.我给了它一些想法,但我没有看到任何方法来分层组织网站,而不会导致父节点在退出时导致低效的重新映射,从而大大打败了HRW的主要优势.

有人知道怎么做这个吗？或者,维基百科是不正确的,在日志时间有一般的方法来实现这一点？

编辑:调查mcdowella的方法:

好的,我想我知道这是如何起作用的.但是你需要比你指定的更多一点.

如果你只是按照你所描述的那样做,你会遇到这样的情况:每个叶子可能只有零个或一个节点,并且叶子最多的子树中有多少个节点存在显着的差异.如果您在每个级别使用HRW进行交换,只需将整个事物设置为常规搜索树,您就会获得完全相同的效果.从本质上讲,你已经实现了一致的散列,以及在桶之间加载不均等的缺陷.计算组合权重,HRW的定义实施,没有增加任何内容; 你最好只是在每个级别进行搜索,因为它可以节省散列,并且可以在不循环每个基数值的情况下实现

但它是可以解决的:您只需要使用HRW从最终级别的许多替代方案中进行选择.也就是说,您需要所有叶节点都在大型桶中,与一致散列中的副本数相当.这些大型桶应相互大致相等,然后您使用HRW选择特定站点.由于存储桶大小是固定的,这是一个O(n)算法,我们得到了所有关键的HRW属性.

老实说,我认为这是值得怀疑的.它不是HRW的实现,因为它只是将HRW与一致的散列相结合.我想这并没有什么不妥,在某些情况下,它甚至可能比使用复制品的常用技术更好.但我认为说明HRW是log(n)是错误的,如果这实际上是作者的意思.

此外,原始描述也值得怀疑.您不需要在每个级别应用HRW,您不应该这样做,因为这样做没有任何优势; 你应该快速做一些事情(比如索引),然后用HRW作最后的选择.

这真的是我们能做的最好的,还是有其他方法来制作HRW O(log(n))？

我对找到平均案例复杂度感到非​​常迷茫，只是提出了一个随机问题......就像。

对于标记顺序搜索，如果概率为 0 <= p <= 1，则找到平均情况。

我得到最坏的情况是 O(n+1)，因为数组中有 n 个元素加上你在最后添加的键的额外元素。如果您立即找到它，最好的情况就是 O(1)。

我真的不想要答案......但更多如何......如果我只是想要答案，我想我只是看看解决方案手册。

它说的是一个O(1)操作的例子是,在一个数组访问的元素.根据一个来源,O(1)可以通过以下方式定义:

[Big-O of 1]表示算法的执行时间不依赖于输入的大小.它的执行时间是不变的.

但是,如果想要访问数组中的元素,操作的效率是否取决于数组中的元素数量？例如

int[] arr = new int[1000000];
addElements(arr, 1000000); //A function which adds 1 million arbitrary integers to the array. 

int foo = arr[55]; 

我不明白最后一个语句如何描述为在O(1)中运行; 数组中的1,000,000个元素是否与运行的运行时间有关？当然,找到元素55需要的时间比元素1要长？如果有的话,这对我来说就像O(n).

我确定我的推理存在缺陷,但是,我只想澄清一下如何在O(1)中运行？

对于 addAll 操作，是否有复杂度为 O(1) 而不是 O(n) 的 Java 集合，还是必须实现我自己的集合？使用有效的链表，Collection1.addAll(Collection2) 操作应该将第二个集合附加到第一个集合，将 collection2 的第一个节点添加到集合 1 的最后一个节点，然后其他的。但这并不是我阅读了似乎使用迭代器的文档，所以我猜复杂度是 O(collection2.size)。

那正确吗 ？