java - 将 N 人分成 K 组：为什么这个算法的大 O 是 O(N^2 * K)？

首先，大 O 表示法让我们了解t(n)/i(n) 当 n -> infinity 时两个函数之间的关系。更具体地说，它是这种关系的上限，这意味着它是f(n) >= t(n)/i(n). t(n)代表花在执行上的时间增长速度，i(n)描述了输入的增长速度。在函数空间中（我们在那里使用函数而不是数字，并且几乎将函数视为数字：例如，我们可以划分或比较它们）两个元素之间的关系也是一个函数。因此，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 -> infinity（为了科学的纯粹性，我们只能在 n -> infinity 时划分和比较函数，但这对方法的实用性没有任何意义）。我们至少可以说（记住它是一个上限）我们算法的执行时间不会比它的输入增长得更快。比如说，我们可能已经得到了时间增长的二次指数速度。在那种情况下t(n)/i(n) = exp^2(n)/exp(n) = a^2n/a^n = exp(n), a > 1，n -> 无穷大，这意味着我们的时间复杂度是 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。这里重要的是商。

第二种方法是理论上的，主要用于分析相对明显的案例。比如说，我们有一段来自示例的代码：

// 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-d 数组dp。它为我们提供了 DP 算法时间复杂度的提示，因为通常我们遍历它一次。然后我们关心数组的大小。它的初始化大小500*500*500并没有给我们太多，因为500它是一个数字，而不是一个函数，严格来说，它不依赖于输入变量。这样做是为了简单。实际上，dp具有的大小k*n*n并假设k <= 500 and n <= 500。

让我们证明一下。Methodstatic int calculate(int pos, int prev, int left, int k)具有三个实际变量pos，prev并且leftwhenk保持不变。范围pos是0 to k因为它从0这里开始return calculate(0, 1, n, k);，基本情况是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增长。在的每个特定值上，通过从加到来改变，在和的每个特定组合值上，通过从减去具有范围的值来改变。01posprev1prevleftposprevleftiprev to leftleft

这种方法背后的想法是，一旦我们通过某种规则迭代输入变量，我们就会得到相应的时间复杂度。例如，我们可以通过在每个步骤上将范围减小两次来迭代一个变量步进元素。在这种情况下，我们会得到对数复杂度。或者我们可以踩到输入的每个元素，然后我们会得到线性复杂度。

换句话说，我们毫无疑问地t(n)/i(n) = 1从常识假设每个算法的最小时间复杂度。这意味着同样t(n)快速i(n)增长。这也意味着我们对输入什么也不做。一旦我们对输入做一些事情，t(n)就会变得f(n)比i(n). 根据前面几行所示的逻辑，我们需要估计f(n).

java - 将 N 人分成 K 组：为什么这个算法的大 O 是 O(N^2 * K)？

问题描述

解决方案

推荐阅读