为什么这个函数的时间复杂度不是O(m!)？
Why the time complexity of this function is not O(m!)?
当我试图找到这个函数的时间复杂度时，我用了m!。
我做的是
T(n,m)=m*T(n-1,m-1)=m(m-1)T(n-2,m-2)=....=m!T(1,1)
但是时间复杂度的答案是O(n)。为什么？
void f3 (int n, int m)
{
if (n <= 1)
return;
if (m > 1)
return m*f3(n-1, m-1);
f3(n-1, m);
}
- 递归终止取决于
n：if (n <= 1) return;
- 有 2 种可能的递归调用：
m*f3(n-1, m-1) 或 f3(n-1, m)。 （二选一）
参数n在每次调用后递减。因此，最多 n 次调用函数 f3.
函数剩余部分的时间复杂度f3是常数。那么总的时间复杂度就是O(n).
我建议您在函数开头添加一个 printf 语句以打印所有调用。这将帮助您了解正在发生的事情。
函数自减n后再次调用自身，所以有N次调用f 具有 O(1) 复杂性，因此 NO(1)=O(N)。您的错误是将 mf(n-1,m-1)* 视为 M 函数 F[ 的调用=20=]。
return 值并未说明函数的复杂性。
复杂性说明 运行 代码需要多少步。
注意
f3(n, m) = 0 如果 n <= 0
f3(n, m) = f3(n-1, m-1) 如果 m > 1
f3(n, m) = f3(n-1, m) 如果 m = 1
f3(n, m) = 0 否则
在第一种情况下，解决方案只需一步。
在第二种情况下，问题被转换为第一种情况或第 3 种情况，然后是第 1 种情况，具体取决于 m 的值。然而，这总是会在 O(n) 中发生。如果 m 大于 O(n) 到第一种情况，否则 O(n) 直到 n 变为 1.
在第 3 种情况下，问题将在 O(n) 中转换为第 1 种情况。
O(1) 中的第 4 种情况。
因此问题是一个 O(n) 问题。
当我试图找到这个函数的时间复杂度时，我用了m!。
我做的是
T(n,m)=m*T(n-1,m-1)=m(m-1)T(n-2,m-2)=....=m!T(1,1)
但是时间复杂度的答案是O(n)。为什么？
void f3 (int n, int m)
{
if (n <= 1)
return;
if (m > 1)
return m*f3(n-1, m-1);
f3(n-1, m);
}
- 递归终止取决于
n：if (n <= 1) return; - 有 2 种可能的递归调用：
m*f3(n-1, m-1)或f3(n-1, m)。 （二选一）
参数n在每次调用后递减。因此，最多 n 次调用函数 f3.
函数剩余部分的时间复杂度f3是常数。那么总的时间复杂度就是O(n).
我建议您在函数开头添加一个 printf 语句以打印所有调用。这将帮助您了解正在发生的事情。
函数自减n后再次调用自身，所以有N次调用f 具有 O(1) 复杂性，因此 NO(1)=O(N)。您的错误是将 mf(n-1,m-1)* 视为 M 函数 F[ 的调用=20=]。
return 值并未说明函数的复杂性。 复杂性说明 运行 代码需要多少步。
注意
f3(n, m) = 0 如果 n <= 0
f3(n, m) = f3(n-1, m-1) 如果 m > 1
f3(n, m) = f3(n-1, m) 如果 m = 1
f3(n, m) = 0 否则
在第一种情况下，解决方案只需一步。
在第二种情况下，问题被转换为第一种情况或第 3 种情况，然后是第 1 种情况，具体取决于 m 的值。然而，这总是会在 O(n) 中发生。如果 m 大于 O(n) 到第一种情况，否则 O(n) 直到 n 变为 1.
在第 3 种情况下，问题将在 O(n) 中转换为第 1 种情况。
O(1) 中的第 4 种情况。
因此问题是一个 O(n) 问题。