这个递归算法的大O是什么
What is the big-O of this recursive algorithm
我们有一个大小为 n 的问题
递归求解大小为 n − 1 的子问题并执行的算法
解决方案的线性工作量。
我尝试使用 plug n chug，发现 big-O 是 n，线性的，但这对我来说似乎不正确。我还能尝试什么？
Mathematics Stack Exchange 的人可能会比我做得更好，但我会试一试。
算法描述有歧义，所以有两种可能：
- 算法对每个子问题执行恒定的工作量。
在这种情况下，该算法实际上将 运行 在
O(n) 时间内（技术上
2n，但常数因子被忽略）。
- 该算法对每个子问题执行线性工作量。
在这种情况下，您正在查看一个线性循环，每个循环都进行线性工作
执行。
n 次执行，n 次执行工作 = O(n^2)。
显然，每次连续执行都减少了工作量，这将
在递归关系解决方案中表现为周围的事物
T(n) = (1/2)n^2，假设我没记错问题的模式。
你提到的递归公式是：
- T(n) = T(n-1) + O(n)
这意味着：
T(n) = kn + k(n-1) + k(n-2) + .. + k，等于 k n * (n + 1) / 2.
所以，算法的复杂度为O(n2).
我们有一个大小为 n 的问题
递归求解大小为 n − 1 的子问题并执行的算法 解决方案的线性工作量。
我尝试使用 plug n chug，发现 big-O 是 n，线性的，但这对我来说似乎不正确。我还能尝试什么？
Mathematics Stack Exchange 的人可能会比我做得更好，但我会试一试。
算法描述有歧义，所以有两种可能：
- 算法对每个子问题执行恒定的工作量。
在这种情况下，该算法实际上将 运行 在
O(n)时间内（技术上2n，但常数因子被忽略）。 - 该算法对每个子问题执行线性工作量。
在这种情况下，您正在查看一个线性循环，每个循环都进行线性工作
执行。
n次执行，n次执行工作 =O(n^2)。 显然，每次连续执行都减少了工作量，这将 在递归关系解决方案中表现为周围的事物T(n) = (1/2)n^2，假设我没记错问题的模式。
你提到的递归公式是：
- T(n) = T(n-1) + O(n)
这意味着：
T(n) = kn + k(n-1) + k(n-2) + .. + k，等于 k n * (n + 1) / 2.
所以，算法的复杂度为O(n2).