把N个人分成K组： 为什么这个算法的大O是O(N^2 * K)？
Divide N people into K groups: Why is the big O of this algorithim O(N^2 * K)?
可以在此处找到问题的描述及其解决方案
https://www.geeksforgeeks.org/count-the-number-of-ways-to-divide-n-in-k-groups-incrementally/
基本上这个问题给了 N 个人，你有多少种方法可以将他们分成 K 组，使得每组的人数大于或等于前一组的人数？
解决办法是递归遍历所有的可能性，复杂度可以从O(NK)降低到O(N2 * K) 通过动态规划。
我了解旧的递归解决方案的复杂性，但无法理解为什么动态规划解决方案具有 O(N2 * K) 的复杂性。关于动态规划解决方案的时间复杂度，人们是如何得出这个结论的？如有任何帮助，我们将不胜感激！
首先，big O notation gives us an idea about the relation between two functions t(n)/i(n) when n -> infinity. To be more specific, it's an upper bound for such relation, which means it's f(n) >= t(n)/i(n). t(n) stands for the speed of growth of time spent on execution, i(n) describes the speed of growth of input. In function space（我们在那里使用函数而不是数字，并且几乎像对待数字一样对待函数：例如，我们可以对它们进行除法或比较）两个元素之间的关系也是一个函数.因此，t(n)/i(n) 是一个函数。
其次，有两种方法可以确定该关系的界限。
科学观察方法 暗示了接下来的步骤。让我们看看用 10 个输入执行一个算法需要多少时间。然后让我们将输入增加到 100 件，然后增加到 1000 件，依此类推。输入的增长速度 i(n) 是指数级的 (10^1, 10^2, 10^3, ...)。假设，我们也得到了时间增长的指数速度（分别为 10^1 秒、10^2 秒、10^3 秒……）。
即t(n)/i(n) = exp(n)/exp(n) = 1，n -> 无穷大（为了科学的纯粹性，只有当n -> 无穷大时，我们才可以划分和比较函数，这对方法的实用性没有任何意义，但).我们至少可以说（记住它是一个上限）我们算法的执行时间不会比它的输入增长得更快。比方说，我们可能已经得到了时间增长的二次指数速度。在那种情况下 t(n)/i(n) = exp^2(n)/exp(n) = a^2n/a^n = exp(n), a > 1, n -> infinity，这意味着我们的时间复杂度是 O(exp(n))，大 O 表示法只是提醒我们这不是一个严格的界限。此外，值得指出的是，我们选择哪种输入增长速度并不重要。我们可能希望线性增加输入。那么t(n)/i(n) = exp(n)*n/n = exp(n)就和t(n)/i(n) = exp^2(n)/exp(n) = a^2n/a^n = exp(n), a > 1表达的一样了。这里重要的是商。
第二种方法是理论上的，主要用于比较明显的案例分析。比如说，我们有一段来自 example:
的代码
// DP Table
static int [][][]dp = new int[500][500][500];
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
static int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
// If the subproblem has been
// solved, use the value
if (dp[pos][prev][left] != -1)
return dp[pos][prev][left];
int answer = 0;
// put all possible values
// greater equal to prev
for (int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return dp[pos][prev][left] = answer;
}
// Function to count the number of
// ways to divide the number N in groups
static int countWaystoDivide(int n, int k)
{
// Intialize DP Table as -1
for (int i = 0; i < 500; i++)
{
for (int j = 0; j < 500; j++)
{
for (int l = 0; l < 500; l++)
dp[i][j][l] = -1;
}
}
return calculate(0, 1, n, k);
}
这里首先要注意的是 3 维数组 dp。它给了我们一个 DP 算法的时间复杂度的提示，因为通常，我们遍历它一次。然后我们关心数组的大小。它用大小 500*500*500 初始化，这并没有给我们很多东西，因为 500 是一个数字，而不是一个函数，严格来说，它不依赖于输入变量。这样做是为了简单起见。实际上，dp 的大小为 k*n*n，假设 k <= 500 and n <= 500.
让我们来证明一下。当k保持不变时，方法static int calculate(int pos, int prev, int left, int k)有三个实际变量pos、prev和left。 pos的范围是0 to k，因为这里是从0开始return calculate(0, 1, n, k);，base case是if (pos == k)，prev的范围是1 to left 因为它从 1 开始并迭代到 left 这里 for (int i = prev; i <= left; i++) 最后 left 的范围是 n to 0 因为它从 n 这里 return calculate(0, 1, n, k); 并向下迭代到 0 这里 for (int i = prev; i <= left; i++)。回顾一下，pos、prev 和 left 的可能组合数就是它们的乘积 k*n*n.
第二件事是证明pos、prev和left的每个区间只遍历一次。从代码中分析这块可以确定：
for (int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
所有 3 个变量仅在此处更改。 pos 通过在每个步骤上添加 1 从 0 增长。在 pos 的每个特定值上，prev 通过从 prev 到 left 添加 1 来更改，在 [=29= 的每个特定值组合上] 和 prev，left 通过从 left.
减去 i 来改变，i 的范围是 prev to left
这种方法背后的想法是，一旦我们按照某种规则迭代输入变量，我们就会得到相应的时间复杂度。例如，我们可以通过在每一步中将范围减小两倍来遍历踩踏元素的变量。在那种情况下，我们会得到对数复杂度。或者我们可以踩踏输入的每个元素，然后我们会得到线性复杂度。
换句话说，我们毫无疑问地从常识上假设了每个算法的最小时间复杂度t(n)/i(n) = 1。这意味着 t(n) 和 i(n) 增长同样快。这也意味着我们对输入什么都不做。一旦我们对输入做了一些事情，t(n) 就会变成 i(n) 的 f(n) 倍。根据前几行所示的逻辑，我们需要估计 f(n).
可以在此处找到问题的描述及其解决方案
https://www.geeksforgeeks.org/count-the-number-of-ways-to-divide-n-in-k-groups-incrementally/
基本上这个问题给了 N 个人，你有多少种方法可以将他们分成 K 组，使得每组的人数大于或等于前一组的人数？
解决办法是递归遍历所有的可能性，复杂度可以从O(NK)降低到O(N2 * K) 通过动态规划。
我了解旧的递归解决方案的复杂性，但无法理解为什么动态规划解决方案具有 O(N2 * K) 的复杂性。关于动态规划解决方案的时间复杂度，人们是如何得出这个结论的？如有任何帮助，我们将不胜感激！
首先，big O notation gives us an idea about the relation between two functions t(n)/i(n) when n -> infinity. To be more specific, it's an upper bound for such relation, which means it's f(n) >= t(n)/i(n). t(n) stands for the speed of growth of time spent on execution, i(n) describes the speed of growth of input. In function space（我们在那里使用函数而不是数字，并且几乎像对待数字一样对待函数：例如，我们可以对它们进行除法或比较）两个元素之间的关系也是一个函数.因此，t(n)/i(n) 是一个函数。
其次，有两种方法可以确定该关系的界限。
科学观察方法 暗示了接下来的步骤。让我们看看用 10 个输入执行一个算法需要多少时间。然后让我们将输入增加到 100 件，然后增加到 1000 件，依此类推。输入的增长速度 i(n) 是指数级的 (10^1, 10^2, 10^3, ...)。假设，我们也得到了时间增长的指数速度（分别为 10^1 秒、10^2 秒、10^3 秒……）。
即t(n)/i(n) = exp(n)/exp(n) = 1，n -> 无穷大（为了科学的纯粹性，只有当n -> 无穷大时，我们才可以划分和比较函数，这对方法的实用性没有任何意义，但).我们至少可以说（记住它是一个上限）我们算法的执行时间不会比它的输入增长得更快。比方说，我们可能已经得到了时间增长的二次指数速度。在那种情况下 t(n)/i(n) = exp^2(n)/exp(n) = a^2n/a^n = exp(n), a > 1, n -> infinity，这意味着我们的时间复杂度是 O(exp(n))，大 O 表示法只是提醒我们这不是一个严格的界限。此外，值得指出的是，我们选择哪种输入增长速度并不重要。我们可能希望线性增加输入。那么t(n)/i(n) = exp(n)*n/n = exp(n)就和t(n)/i(n) = exp^2(n)/exp(n) = a^2n/a^n = exp(n), a > 1表达的一样了。这里重要的是商。
第二种方法是理论上的，主要用于比较明显的案例分析。比如说，我们有一段来自 example:
的代码// DP Table
static int [][][]dp = new int[500][500][500];
// Function to count the number
// of ways to divide the number N
// in groups such that each group
// has K number of elements
static int calculate(int pos, int prev,
int left, int k)
{
// Base Case
if (pos == k)
{
if (left == 0)
return 1;
else
return 0;
}
// if N is divides completely
// into less than k groups
if (left == 0)
return 0;
// If the subproblem has been
// solved, use the value
if (dp[pos][prev][left] != -1)
return dp[pos][prev][left];
int answer = 0;
// put all possible values
// greater equal to prev
for (int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
return dp[pos][prev][left] = answer;
}
// Function to count the number of
// ways to divide the number N in groups
static int countWaystoDivide(int n, int k)
{
// Intialize DP Table as -1
for (int i = 0; i < 500; i++)
{
for (int j = 0; j < 500; j++)
{
for (int l = 0; l < 500; l++)
dp[i][j][l] = -1;
}
}
return calculate(0, 1, n, k);
}
这里首先要注意的是 3 维数组 dp。它给了我们一个 DP 算法的时间复杂度的提示，因为通常，我们遍历它一次。然后我们关心数组的大小。它用大小 500*500*500 初始化，这并没有给我们很多东西，因为 500 是一个数字，而不是一个函数，严格来说，它不依赖于输入变量。这样做是为了简单起见。实际上，dp 的大小为 k*n*n，假设 k <= 500 and n <= 500.
让我们来证明一下。当k保持不变时，方法static int calculate(int pos, int prev, int left, int k)有三个实际变量pos、prev和left。 pos的范围是0 to k，因为这里是从0开始return calculate(0, 1, n, k);，base case是if (pos == k)，prev的范围是1 to left 因为它从 1 开始并迭代到 left 这里 for (int i = prev; i <= left; i++) 最后 left 的范围是 n to 0 因为它从 n 这里 return calculate(0, 1, n, k); 并向下迭代到 0 这里 for (int i = prev; i <= left; i++)。回顾一下，pos、prev 和 left 的可能组合数就是它们的乘积 k*n*n.
第二件事是证明pos、prev和left的每个区间只遍历一次。从代码中分析这块可以确定：
for (int i = prev; i <= left; i++)
{
answer += calculate(pos + 1, i,
left - i, k);
}
所有 3 个变量仅在此处更改。 pos 通过在每个步骤上添加 1 从 0 增长。在 pos 的每个特定值上，prev 通过从 prev 到 left 添加 1 来更改，在 [=29= 的每个特定值组合上] 和 prev，left 通过从 left.
i 来改变，i 的范围是 prev to left
这种方法背后的想法是，一旦我们按照某种规则迭代输入变量，我们就会得到相应的时间复杂度。例如，我们可以通过在每一步中将范围减小两倍来遍历踩踏元素的变量。在那种情况下，我们会得到对数复杂度。或者我们可以踩踏输入的每个元素，然后我们会得到线性复杂度。
换句话说，我们毫无疑问地从常识上假设了每个算法的最小时间复杂度t(n)/i(n) = 1。这意味着 t(n) 和 i(n) 增长同样快。这也意味着我们对输入什么都不做。一旦我们对输入做了一些事情，t(n) 就会变成 i(n) 的 f(n) 倍。根据前几行所示的逻辑，我们需要估计 f(n).