问题标签 [asymptotic-complexity]

这是我的功能。这是一个简单的答案，我只是对答案没有信心。

现在，为了获得复杂性，我这样做：

T(n) = T(n/2) + O(1)

T(n/2) = T(n/4) + O(1)

...

T(1) = O(1)

现在，添加方程，我得到

T(n) = O(1) + O(1)...

那么最终答案是什么？

我正在研究随机快速排序算法。我意识到这个算法的运行时间总是表示为“预期运行时间”。

指定或使用“预期运行时间”的原因是什么？为什么我们不计算最坏或平均情况？

谁能帮我分析以下伪代码的运行时间

我看到它的下限是 omega(n^3)，因为如果外部 for 循环内部只是 theta(1)，那就是它的样子。

我对仅在外循环的前 n 次迭代中运行的内循环感到困惑。我是否只是平均内部循环的运行时间：n^3 * ((1/n^2)*n + (1/n)*1，在这种情况下它是 O(n^3)？

我在准备考试时遇到了这个问题。

给定两个数字数组 a1,..., an 和 b1,....,bn，其中每个数字为 0 或 1，找到最大跨度 (i,j) 的最快算法使得 , ai + ai+1 +....+aj = bi + bi+1 +....+bj 或报告没有这样的跨度。

(A) 如果允许散列，则需要 O(3^n) 和 omega(2^n) 时间。

(B) 在关键比较模式下需要 O(n^3) 和 omega(n^2.5) 和时间

(C) 占用 theta(n) 时间和空间

(D) 仅当 2n 个元素之和为偶数时才花费 O(square-root(n)) 时间。

假设我们有一个包含 n 个元素的二叉堆，并希望插入 n 个更多元素（不一定一个接一个）。这需要多少时间？

我认为它是θ（n logn），因为一次插入需要logn。

构建类层次结构的某些方法是否比其他方法更有效？有没有办法测量这个？设计模式如何影响计算复杂性？我只是在想这个错误吗？只是好奇。

我有这个复发：

我的尝试如下：

树是这样的：

• 树的高度：(n/(2 ^h ))-1 = 1 ⇒ h = lg n - 1 = lg n - lg 2
• 最后一级的成本：2 ^h = 2 ^{lg n - lg 2} = (1/2) n
• 直到级别 h-1 的所有级别的成本：Σ _{i=0,...,lg(2n)} n - (2 ⁱ -1)，这是一个几何级数，等于 (1/2)((1/2 )n-1)

所以，T(n) = Θ(n lg n)

我的问题是：对吗？

这个表达式f ( n ) = 2 ^{O ( n )}是什么意思？

我正在自学动态编程。这几乎是神奇的。不过实话说。无论如何，我解决的问题是：Given a stairs of N steps and a child who can either take 1, 2, or 3 steps at a time, how many different ways can the child reach the top step?。问题并不难，我的实现如下。

但是，现在我想获得运行时。我该如何解决这个问题？我对 Akra-Bazzi 和 Master Theorem 很熟悉（仅此而已）。这些在这里适用吗？

http://en.wikipedia.org/wiki/Master_theorem

在这里它似乎可能是：T(N) = 3 * T(???) + O(1)但我真的不确定。

多谢你们。

^{我了解渐近符号的原理，例如，当某事物为 O(1) 或 O(n 2} )时，我明白它的含义。但是 O(log n) 是什么意思呢？或 O(n log n) 例如？