问题标签 [asymptotic-complexity]

我想计算给定算法的运行时间 O(n, x) = Theta(n, x) 取决于 n 和 x 大量（> 100）个示例（算法需要多长时间 n 和 x ）。实际上有办法做到这一点吗？

我知道运行时间会随着 n 和 x (!) 的增加而增加，但我认为连贯性太复杂了，无法通过“手动”计算出 O(n, x)，因为 n 或 x mac 会像 n ^ x 一样增加，或者更糟。

顺便提一句。我最喜欢解决这个问题的语言是 Python 或 PHP。

我想知道以下算法的时间复杂度。乍一看，时间复杂度看起来是 O(n^5)，这就是我在互联网上看到的大多数网站中提到的。但仔细分析似乎给出了不同的答案，下面是代码：

有人walk me through可以找到这些的运行时间吗？对于foo，我的猜测是这是O(n^2)由于 2 次递归调用。也可以Θ(n^2)吗？

因为bar，我不知道，因为它是无限递归。

考虑以下算法：

我有兴趣找出这个算法执行了多少加法和乘法运算；但是，我遇到了麻烦。我知道每次迭代后 i 的值加倍，但我不知道如何推广算法以给出正确数量的操作，直到 n 的值。如果有人能对这个问题有所了解，我将不胜感激。

谢谢！

正如您在此链接中看到的那样：http ://en.wikipedia.org/wiki/D-ary_heap#Applications 它在维基百科中说 d 的最佳选择是 d=m/n （它导致总时间复杂度为O(m logm/nn) )

在我看来，这个猜测是凭空捏造的。有没有一种简单的方法可以证明（甚至解释）这确实是最优的 d ？

提前致谢

我在准备面试时发现了以下问题：

3可以写成1+1+1、1+2、2+1；4可以写成1+1+1+1、1+1+2、2+2、1+2+1、2+1+1、3+1、1+3；给定一个整数，存在多少个可能的表达式？（1+2和2+1不同）

因此，编写一个蛮力算法来计算它并获得所有执行它的数字集的集合是相当简单的：

现在我相信描述这个算法复杂性的递归关系是：

我不太确定如何从这种递归关系中得出很大的复杂性。我还想知道这个问题是否有一个封闭形式的解决方案（每个数字我们会有多少这样的组合）。

我也不确定如果我们通过缓存每个调用的结果来记忆这个算法（类似于如何加速斐波那契），那么复杂性会是多少。

我不知道如何在 3 个 PHP 数组中找到所有“对”和“三元组”。我的数组如下所示：

这些数组有 3 个；它们始终按整数键排序，并且始终包含 10 个索引 (0-9)。我想做的是：

• 在两个数组或所有 3 个数组中查找相同名称的实例（通过比较“清理”字段），并将它们的“颜色”更改为相同（即我不想只找到所有 3 个之间的交集数组 - 可以用 array_intersect 完成）
• 构建第 4 个数组，该数组连接所有条目并通过将它们的权重相加来组合相同的名称（通过比较“清理”字段）（颜色无关紧要）
• 由于这些任务是相似的，我想同时做它们，并尽量减少复杂性

这很难解释，所以我在视觉上表示它。

颜色：

颜色 http://www.tsiomenko.com/1.png

重量：

重量 http://www.tsiomenko.com/2.png

我有一些工作代码，但它真的很长、很丑，并且具有 N^3 的复杂性——我使用嵌套的 for 循环多次遍历所有数组，直到我得到我需要的东西。尽管我正在使用非常小的数组，但我想知道如何有效地做到这一点，因为我很好奇其他人将如何解决这个问题。欢迎使用有关如何解决此问题的伪代码，而不是 PHP。

我正在准备考试，这些是去年考试中的一些问题。任务是计算精确复杂度和渐近复杂度。你会怎么解决？普遍，如果可能的话。

提前致谢

我一直在尝试计算以下函数的复杂性：

具体来说，while 循环的复杂性。有人告诉我 g(n) 的复杂性是 O(n)，但我不确定它的复杂性是多少，以及我将如何解决它。我已经意识到复杂度不会是 O(0.5n^2)，但我不确定如何计算它，因为每次减半。有人有想法么？

我对 Master Theorem 有点耳目一新，我试图找出一种算法的运行时间，该算法n通过递归解决 2 个大小子问题n-1并在恒定时间内组合解决方案来解决大小问题。
所以公式是：
T(N) = 2T(N - 1) + O(1)
但我不确定如何制定主定理的条件。我的意思是在这种情况下
我们没有主定理公式吗？ 如果是的话，因为很明显，因为我在哪里可以理解这一点？假设我到目前为止是对的？T(N/b)bb=N/(N-1)
a > b^kk=0O(N^z)z=log2(N/N-1)