问题标签 [asymptotic-complexity]

我有一个关于IP和FP性能的问题。假设我有一个计算第 n 个斐波那契数的函数。

在命令式编程中，我可以选择使用迭代方式、递归或动态编程来计算第 n 个斐波那契数。当然，与渐近递归相比，迭代方式和动态规划会表现得更好。

在函数式编程中，假设不涉及状态，那么我只能以递归方式进行。

在这种情况下，这是否意味着与命令式编程相比，函数式编程在效率（渐近）方面的性能总是相同或更慢？

现实世界的函数式编程如何处理这个问题？

我正在尝试使用 Big O 表示法找出 for 循环的复杂性。我以前在我的其他课程中也这样做过，但是这个比其他的更严格，因为它是在实际算法上的。代码如下：

和

我已经知道第一个循环的复杂度为 O(n)，因为它正在遍历列表 n 次。至于第二个循环，我有点失落。我相信对于每个被测试的 n ，它都会经过 i 次循环。我（错误地）假设这意味着每次评估循环都是 O(n*i) 。我的假设中有什么遗漏的吗？我知道 cnt++ 是常数时间。

感谢您在分析中的帮助。每个循环都在自己的空间中，它们并不在一起。

如果一个算法有两个子算法，当子算法 A1 对给定输入最好的情况下，它是子算法 A2 的最坏情况。我怎样才能找到整体算法的复杂性？我的意思是Ω（N）+ O（N）=？我知道算法是否按顺序执行顺序，总体复杂度为 O(N)+ O(N)，嵌套顺序为 O(N)* O(N)。

请告诉我在这两种情况下，按顺序和嵌套顺序

我试图按照从低复杂度到高复杂度的大 O 复杂度来排序以下函数：4^(log(N)), 2N, 3^100, log(log(N)), 5N, N!, (log(N))^2

这：

1. 3^100
2. log(log(N))
3. 2N
4. 5N
5. (log(N))^2
6. 4^(log(N))
7. N!

我只是通过使用维基百科上给出的图表来解决这个问题。有没有办法验证答案？

如果数组中至少有两个值是，则该方法hasTwoTrueValues返回。为建议的所有三个实现提供 Big-O 运行时间。truebooleantrue

//版本 1

//版本 2

//版本 3

这些是我的答案：

• 版本 1是O(n)
• 版本 2是O(n^2)
• 版本 3是O(n^2)

我对这个 Big-O 表示法真的很陌生，所以如果我的答案是正确/不正确的，我需要指导。如果我错了，你能解释一下并帮助我学习吗？

我们能解决这个 T(n) = 2T( n/2 ) + n lg n递归方程主定理吗？我来自一个链接，他说我们不能在这里应用主定理，因为它不满足任何 3ree 案例条件。另一方面，他采取了另一个例子 T(n) = 27T(n/3) + Θ(n^3 lg n) 并找到了封闭的解决方案theta(n^3logn) 为了解决这个问题，他使用了主定理的第二种情况If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 在这里我产生了困惑，为什么我们不能在这里应用第二种情况，而它完全适合第二种情况。 我的想法： a = 2 , b =2; let k =1 then f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) 但是正如上面提到的我们不能应用主定理我很困惑为什么不.

注意：这是由于 f(n) bcz in和 in * * 如果我在这里错了，请纠正我。T(n) = 2T( n/2 ) + n lg n f(n) = nlog nT(n) = 27T(n/3) + Θ(n^3 lg n)f(n) = theta(n^3log n)

这是var_dump我的数组：

（只是为了好玩，我在这段代码中包含了两个双关语，试着找到它们！）

如何将此数组拆分为两个数组，一个包含所有quacks; 另一个Aaaaarrrrrggggghhhhh？

请注意，它并不总是按连续顺序排列，因此可能会考虑嵌套的哈希图，例如：

1. 查看if (isset($myarr['$found_val']))
2. 如果找到，则附加该数组
3. 否则用一个新数组创建那个地方

但不确定数组是如何实现的，所以可能是 O(n) 追加，在这种情况下我需要一些其他的解决方案......

假设我有一个完整的二叉树，直到一定深度d。遍历（前序遍历）这棵树的时间复杂度是多少。

我很困惑，因为我知道树中的节点数量是 2^d，所以时间复杂度是BigO(2^d)？因为这棵树呈指数增长。

但是，在互联网上的研究中，每个人都说遍历是BigO(n)其中 n 是元素的数量（2^d在这种情况下是），而不是BigO(2^d)，我错过了什么？

谢谢

我一直在对二叉树和数组列表表示进行一些研究。我很难理解最坏情况下的空间复杂度是 O(2^n)。具体来说，这本书指出，空间使用量为 O(N)（N = 数组大小），在最坏的情况下为 O(2^n)。我原以为在最坏的情况下它会是 2n，因为每个节点都有两个子节点（索引）而不是 O(2^n)，其中 n = 否。的元素。

例如，如果我有一个有 7 个节点的二叉树，那么空间将是 2n = 14 而不是 2^n = 128。

如果我有一个算法，输入只是一个数字，输出是它的一组除数。所以我的输入将永远是一个数字，算法中的迭代次数将取决于数字有多大。会是什么这种算法的大符号？算法：