递归数置换时间复杂度

文章/答案/技术大牛

发布

2回答

递归函数的复杂性-时间和空间

algorithm、complexity-theory

我感兴趣的是如何计算递归函数的时间和空间复杂度，如置换、斐波那契(描述为)谢谢

浏览 0提问于2010-12-02得票数 4

回答已采纳

1回答

java、time-complexity

我想出了一段递归生成数字排列的代码，但不确定时间复杂度，有人知道它是什么吗？

浏览 17提问于2019-04-13得票数 2

回答已采纳

1回答

置换算法的大O分析

python-3.x、algorithm、big-o

result = False global result if a==b: else: a[l], a[i] = a[i], a[l] a[l], a[i] = a[i], a[l] string2 =

浏览 0提问于2019-02-03得票数 9

回答已采纳

1回答

这个排列算法的空间复杂度是多少？

algorithm、big-o、permutation

这个算法用于递归计算排列的时间复杂度应该是O(n!*n)，但我不能100%确定空间复杂性。存在n递归，递归所需的最大空间是n (每个置换的空间* n! (排列数目))。算法的空间复杂度是O(n!

浏览 1提问于2016-11-14得票数 0

回答已采纳

1回答

这种回溯算法寻找排列的时间复杂度是多少？

python、algorithm、time-complexity、backtracking

我试图确定我创建的这个算法的时间和空间复杂性，以查找Python中数组的所有排列。时间复杂度O(sum_{k=1}^N P(n，k))，其中P(n，k)是k因子的置换吗？

浏览 14提问于2021-12-18得票数 0

1回答

最小跳跃数组递归时间复杂度应为O(n^n)或O(n!)

java、arrays、algorithm、time-complexity

我正在检查GeekforGeeks <code>C0</code>中的“到达终点的最小跳跃数”问题。我对这里提到的时间复杂度感到困惑，它是O(n^n)。<code>A1</code>

浏览 14提问于2021-06-15得票数 3

回答已采纳

2回答

置换计算运行时复杂度的一些变化

python、algorithm、time-complexity、permutation

关于标准置换查找算法的运行时复杂性，我有一个问题。考虑一个列表A，查找(并打印)其元素的所有排列。下面是我的递归实现，其中printperm()打印每个置换： if len(A) == len(p): print("".join(p)其中n是A的大小，这是因为在每个递归级别上，工作量减少了1。所以，最高的递归级别是n个工作量，下一个级别是n-1，下一个级别是n-2，依此类推。所以总复杂度是n*(n-1)

浏览 0提问于2018-09-09得票数 1

回答已采纳

3回答

用动态规划计算第N个斐波那契数的时间复杂度是多少？

algorithm、recursion、time-complexity、dynamic-programming、fibonacci

我最近使用递归解决了Fibonacci算法的时间复杂性。这是一个时间复杂度为O(2^n)的标准解决方案。我想知道如果你使用DP算法，它保存了已经计算过的斐波那契数，时间复杂度会是多少？谢谢!

浏览 0提问于2020-07-06得票数 0

1回答

排列算法的复杂性分析

algorithm、recursion、time-complexity、computer-science、space-complexity

我试图理解生成数组排列的算法的时间和空间复杂性。，其中n是要置换的元素数，并进行n递归调用。因此，运行时间似乎符合递归关系T(n)=nT(n-1)+n=n[(n-1)T(n-2)+(n-1)]+n=...=n+n(n-1)+n(n-1)(n-2)+...+n!=n![1/(n-1)!e，因此时间复杂度为O(n!)，空间复杂度为O(max(n!, n))，其中n!是排列的总数，n是递归树的高度。这个问题取自编程访谈书中的元素

浏览 0提问于2021-11-14得票数 0

回答已采纳

1回答

BFS:递归与迭代

recursion、tree、iteration、binary-tree、breadth-first-search

用递归和迭代的方式编写BFS树遍历算法有什么好处吗？在我看来，迭代是可行的，因为它可以在一个简单的循环中实现：递归有什么好处吗？它似乎更复杂，没有任何优势。

浏览 1提问于2018-03-07得票数 4

6回答

求阶乘的有效方法

c++、data-structures

除了正规的递归函数和循环方法外，还有什么有效的方法来找出一个数的阶乘？由于通常的方法产生输出所需的时间太长，那么有什么方法比递归和循环方法更能降低时间复杂度呢?如果不是，为什么？

浏览 1提问于2013-08-21得票数 1

回答已采纳

1回答

给定字符串的所有排列.复杂性

javascript、algorithm

我有一个关于这个解的时间和空间复杂性的问题。我假设时间复杂度将是O(n)，因为嵌套循环和递归，空间复杂度将是O(N)，因为递归。我的假设正确吗？如果是，是否有更好的性能解决方案？

浏览 0提问于2018-03-28得票数 2

回答已采纳

1回答

使用dp具有特定条件的可能数组的数目

algorithm、dynamic-programming

如果数组中的每个数字都可以被前一个数除以，那么1和n之间增加的自然数的数组称为美丽。使用动态规划，问题是找到具有给定时间复杂度的大小为k的漂亮数组的数量：对于第一个问题，我能想到的是，一个数字的除数可以用O(root(n))时间复杂度来确定我想设计一个递归算法来计算每个i < k的可能数组数，但我不知道如何计算。

浏览 1提问于2021-03-27得票数 1

回答已采纳

1回答

计算2^5000的时间复杂度是多少？

algorithm、recursion、time-complexity

计算2^5000的时间复杂度是多少？我用递归的方法逼近它，但是它导致了O(N)，其中N=一个数的幂。有没有办法降低这个时间的复杂性？

浏览 3提问于2016-10-12得票数 0

回答已采纳

2回答

将置换转换为逆表示

algorithm、time-complexity、permutation、inversion

第一个N自然数的置换N可以用 I = [i1, i2, ... , iN]的列表来表示，其中iK可以告诉我们在排列P中K之前可以找到多少个大于K的数字。有一种明显的算法可以将置换从标准形式转换为反转形式，并在O(N^2)中运行(我们只需遵循定义和计数)。同样的情况也适用于逆转换(这稍微不那么直接)。有没有一种时间复杂度较低的算法？

浏览 0提问于2016-01-06得票数 1

回答已采纳

3回答