标签: big-o

我很快就会教"Java崩溃课程".虽然假设观众成员会知道Big-O表示法可能是安全的,但假设他们知道各种集合实现的各种操作的顺序是什么可能是不安全的.

我可以花时间自己生成一个摘要矩阵,但如果它已经在公共领域的某个地方出现,我肯定想重复使用它(当然还有适当的信用.)

任何人有任何指针？

显然;-)标准容器提供某种形式的保证.

什么类型的保证以及不同类型的容器之间究竟有什么区别？

从工作的SGI页(约STL)我想出了这一点:

Container Types:
================
Container:
    Forward Container
        Reverse Container
            Random Access Container
    Sequence
        Front Insert Sequence
        Back  Insert Sequence
    Associative Container
        Simple   Associative Container
        Pair     Associative Container
        Sorted   Associative Container
        Multiple Associative Container

Container Types mapped to Standard Containers
=============================================

std::vector:    Sequence    Back        Sequence                    Forward/Reverse/Random Container
std::deque:     Sequence    Front/Back  Sequence                    Forward/Reverse/Random Container
std::list:      Sequence    Front/Back  Sequence                    Forward/Reverse Container
std::set:       Sorted/Simple/Unique    Associative Container       Forward Container
std::map:       Sorted/Pair/Unique      Associative Container       Forward Container
std::multiset:  Sorted/Simple/Multiple  Associative Container …

我已经看到了一些关于SO re Java hashmaps及其O(1)查找时间的有趣声明.有人可以解释为什么会这样吗？除非这些哈希图与我买的任何哈希算法有很大的不同,否则必须始终存在包含冲突的数据集.

在这种情况下,查找将是O(n)而不是O(1).

有人可以解释他们是否是 O(1),如果是,他们如何实现这一目标？

这会被归类为"Hello,World!"的O(1)算法吗？??

public class Hello1
{
   public static void Main()
   {
      DateTime TwentyYearsLater = new DateTime(2035,01,01);
      while ( DateTime.Now < TwentyYearsLater )
      { 
          System.Console.WriteLine("It's still not time to print the hello ...");
      }
      System.Console.WriteLine("Hello, World!");
   }
}

我正在考虑使用

DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{ 
   // ... 
}

代码片段作为一个繁忙的循环,当有人要求某种复杂性的算法时,它就像一个笑话.这是正确的吗？

假设我们得到一个n个整数的数组,代表一天的股票价格.我们希望找到一对(buyDay,sellDay) ,与buyDay≤sellDay,例如,如果我们买了股票buyDay卖了上sellDay,我们将最大限度地提高我们的利润.

显然,通过尝试所有可能的(buyDay,sellDay)对并从所有这些对中充分利用,该算法有一个O(n ²)解决方案.但是,是否有更好的算法,也许是在O(n)时间运行的算法？

我已经看到这个术语"O(1)访问时间"曾经意味着"快速",但我不明白这意味着什么.我在同一个上下文中看到的另一个术语是"O(n)访问时间".有人可以用简单的方式解释这些术语的含义吗？

也可以看看

• 什么是大O符号？你用它吗？
• 8岁儿童的大O？

哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:

答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.

B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).

除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.

我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.

维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？

编辑:总结我学到的东西:

• 这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.

• 在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.

我对big-O的了解是有限的,当日志术语出现在等式中时,它会让我更加惊讶.

有人可以用简单的语言向我解释O(log n)算法是什么吗？对数来自哪里？

当我试图解决这个中期练习题时,这个问题就出现了:

设X(1..n)和Y(1..n)包含两个整数列表,每个整数按非递减顺序排序.给出O(log n)-time算法以找到所有2n个组合元素的中值(或第n个最小整数).例如,X =(4,5,7,8,9)和Y =(3,5,8,9,10),那么7是组合列表的中位数(3,4,5,5,7) ,8,8,9,9,10).[提示:使用二分搜索的概念]

通过添加和删除项目,可以非常轻松地修改JavaScript中的数组.它有点掩盖了大多数语言数组是固定大小的事实,并且需要复杂的操作来调整大小.似乎JavaScript可以很容易地编写性能不佳的数组代码.这导致了一个问题:

在数组性能方面,我可以从JavaScript实现中获得什么样的性能(就大O时间复杂度而言)？

我假设所有合理的JavaScript实现至少具有以下大O.

• 访问 - O(1)
• 附加 - O(n)
• 前期 - O(n)
• 插入 - O(n)
• 删除 - O(n)
• 交换 - O(1)

JavaScript允许您使用new Array(length)语法将数组预填充到特定大小.(额外的问题:以这种方式创建一个数组O(1)或O(n))这更像是一个传统的数组,如果用作预先调整大小的数组,可以允许O(1)追加.如果添加了循环缓冲逻辑,则可以实现O(1)前置.如果使用动态扩展数组,则O(log n)将是这两者的平均情况.

对于某些事情,我可以期待比我的假设更好的表现吗？我不希望在任何规范中概述任何内容,但实际上可能是所有主要实现都在后台使用优化的数组.是否有动态扩展阵列或其他一些性能提升算法？

PS

我想知道这个的原因是因为我正在研究一些排序算法,其中大多数似乎假设在描述它们的整体大O时附加和删除是O(1)操作.

根据关于链表的维基百科文章,在链表中间插入被认为是O(1).我认为这将是O(n).您是否需要找到可能接近列表末尾的节点？

此分析是否不考虑节点操作的发现(虽然它是必需的)并且只是插入本身？

编辑:

链接列表与数组相比有几个优点.在列表的特定点处插入元素是恒定时间操作,而在数组中插入可能需要移动一半或更多元素.

上述陈述对我来说有点误导.如果我错了,请纠正我,但我认为结论应该是:

阵列:

• 找到插入/删除点O(1)
• 执行插入/删除O(n)

链接列表:

• 找到插入/删除点O(n)
• 执行插入/删除O(1)

我认为你唯一一次不必找到位置就是你保留了某种指针(如某些情况下的头部和尾部).因此,我们不能断然说链接列表总是超过插入/删除选项的数组.