递归关系T（n）=T（n-1）*n的时间复杂度
我需要以下递归关系的帮助。
T（1）=1
T（n）=T（n-1）*n
这就是我尝试过的。我想我可能把替换部分搞砸了，但请再看一次，让我知道我得到的时间复杂度是否正确。
T(n) = T(n-1)*n T(n-1) = T(n-2)*n-1
T(n) = [T(n-2)*(n-1)]*n
T(n) = T(n-2)*(n-1)*n
T(n) = [T(n-3)*n-2]*(n-1)*n
T(n) = T(n-3)*(n-2)*(n-1)*n
...
...
...
T(n) = T(n-k)*(n-(k-1))*(n-(k-2))...*(n-1)*(n)
Assuming n-k=0, n=k
T(n) = T(n-n)*(n-n+1)*(n-n+2)...*(n-1)*(n)
T(n) = T(0)*(1)*(2)...*(n-1)*n
O(n^2)
现在我不确定我所做的是否完全正确，但如果有任何帮助，我将不胜感激。
共有2个答案
非常接近！您已经正确识别出复杂性是
n*（n-1）*（n-2）*…*3 * 2 * 1.
然而，这不是O（n2）。如果您添加这些项而不是将它们相乘，则为O（n2）。
从1到n的所有自然数的乘积叫什么？
只有最终的复杂性是错误的，你最终得到O（n！）。
递归关系必须为T（n）=T（n-1）n，以获得O（n^2）作为复杂性。
-
我明天有一个计算机科学期中考试，我需要帮助确定一个特定递归函数的复杂性，如下所示，这比我已经研究过的东西要复杂得多：它有两个变量 T（n）=3 mT（n-m） 在m为常数的简单情况下，可以通过编写解包关系轻松获得公式；然而，在这种情况下，拆包并不会使生活变得更容易，如下所示（假设t（0）=c）： T（n）=3 mT（n-m） T（n-1）=3 mT（n-m-1） T（n-2）=3 mT（n-m-2
-
我在GeekforGeekshttps://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对这里提到的时间复杂度感到困惑，它是O（n^n）。 如果我看到上面的代码块，minJumps（arr，I，h）递归调用是从I=l1调用的。所以在每个递归步骤中，l（
-
两者的区别是什么 和 ？ 第一个语句的输出是 [0 0…n次] 而第二个是 ([0] [0] .... n行）
-
问题内容： 我刚刚开始学习数据结构，并且在进行数组插入时想知道为什么数组插入的时间复杂度为O（n）而不是O（n + 1）？ 在最佳情况下，当插入在最后时，时间复杂度为O（1）。我想我们正在考虑1插入元素，因为这里没有元素被移动。在最坏的情况下，假设我们必须移动n个元素然后插入新元素，那么时间时间复杂度是否应该为O（n + 1）？n用于移动元素，1用于插入。 非常感谢您的帮助。 问题答案： O（n）
-
我试图为这段代码找出一个大O的紧密界限： 如果我们从内最循环开始，它将在最坏的情况下运行k=n^2次，占O（N^2）。如果语句每次j=m*i时都为真，其中m是一个任意常数。由于j从1运行到i^2，这将在m={1,2，...，i}时发生，这意味着它将在i次时为真，i最多可以是n，所以最坏的情况将是m={1,2，...，n}=n次。如果i=n，第二个循环应该有O（N^2）的最坏情况。外环具有O（N）的
-
描述一个O（n logn）-时间算法，给定一组由n个整数和另一个整数x组成的S，该算法确定S中是否存在两个元素，其和正好是x。 我计划用二进制搜索来搜索这个。 我如何找到这个算法的时间复杂度？如果T（n）不是（n log n），正确的算法是什么？