标签: time-complexity

我发现时间复杂度的资源还不清楚何时可以忽略时间复杂度方程中的项,特别是非多项式的例子.

我很清楚,给定n ² + n + 1 形式的东西,最后两个术语是无关紧要的.

具体来说,给定两个分类,2 ⁿ和n*(2 ⁿ),是第二个与第一个相同的顺序？额外的n乘法是否重要？通常资源只是说x ⁿ处于指数状态并且增长得更快......然后继续前进.

我可以理解为什么它不会因为2 ⁿ将大大超过n,但因为它们没有被加在一起,所以在比较两个方程时它会很重要,实际上它们之间的差异总是n的因子,这似乎至少可以说是重要的.

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

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

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

我听说有人说由于二进制搜索将搜索所需的输入减半,因此它是log(n)算法.由于我不是来自数学背景,所以我无法与之相关.有人可以更详细地解释一下吗？是否必须对对数系列做些什么？

BFS的基本算法:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

所以我认为时间的复杂性将是:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

v顶点1到哪里n

首先,我说的是正确的吗？其次,这是怎样的O(N + E),直觉为什么会非常好.谢谢

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

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

我们每天使用的具有O(1),O(n log n)和O(log n)复杂度的算法是什么？

我对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(log n)复杂性的一些因素.

什么会导致算法具有时间复杂度O(log log n)？

什么是假多项式时间？它与多项式时间有何不同？在伪多项式时间运行的一些算法具有运行时间,如O(nW)(对于0/1背包问题)或O(√n)(对于试验除法); 为什么不算作多项式时间？