我的groupThePeople代码时间复杂度是O(n)还是O(n*m)？

我写了下面这段Java代码来解决按组大小分组人的问题，原本以为它的时间复杂度是O(n)，但因为里面有一个内层while循环，我开始疑惑会不会是O(n*m)（m是组的数量），想请大家帮忙确认它的正确时间复杂度。

public List<List<Integer>> groupThePeople(int[] groupSizes) { 
    List<List<Integer>> groups = new ArrayList<List<Integer>>(); 
    for(int i = 0; i < groupSizes.length; i++) { 
        boolean added = false; 
        int index = 0; 
        while(index < groups.size() && !added) { 
            List<Integer> temp = groups.get(index); 
            int size = groupSizes[temp.get(0)]; 
            if(size == groupSizes[i] && temp.size() < groupSizes[i]) { 
                temp.add(i); 
                added = true; 
            } else { 
                index++; 
            } 
        } 
        if(!added) { 
            ArrayList<Integer> temp = new ArrayList<Integer>(); 
            temp.add(i); 
            groups.add(temp); 
        } 
    } 
    return groups; 
}

别担心，这段代码的时间复杂度确实是O(n)，原因如下：

• 虽然存在嵌套循环，但每个元素只会被处理一次：每个索引i最终只会被添加到某一个组中，一旦添加成功，就不会再参与后续的内层循环判断。
• 内层循环的总迭代次数是线性的：我们把所有内层循环的迭代次数加总，会发现它和数组长度n是线性相关的。每个组在满员后就不会再被后续元素匹配，比如当组大小为k时，每个组最多被检查k次，而总组数最多是n/k，两者相乘总检查次数还是n；就算所有组大小都是1，内层循环每次只检查一个组，总操作数依然是O(n)。

所以整体来看，这段代码的时间复杂度是线性的O(n)，其中n是groupSizes数组的长度。

内容的提问来源于stack exchange，提问作者Littleboitien