求数组的数组的笛卡尔积的时间复杂度（附Java实现代码）

让我们一步步拆解这段Java代码的时间复杂度，先搞清楚代码的核心逻辑：

这段代码的目标是生成多个字符串数组的笛卡尔积并打印出来，主要分为两个核心步骤：

1. 计算总组合数 #

第一个for循环遍历输入的所有集合（sets数组），将每个集合的长度相乘，得到笛卡尔积的总组合数combinations。假设输入有n个集合，这个循环会执行n次，时间复杂度是 O(n)。

2. 生成并打印每个组合 #

外层for循环会执行combinations次（也就是笛卡尔积的总元素个数），每次循环内部又会遍历所有n个集合，通过计算(i/j)%set.length来定位当前组合中每个集合对应的元素，然后打印。

这里的关键是：

• 外层循环次数 = 总组合数C = k₁ * k₂ * ... * kₙ（其中kᵢ是第i个集合的元素数量）
• 内层每次循环执行n次操作

所以这部分的时间复杂度是 O(C * n)。

总时间复杂度 #

把两部分加起来，总时间复杂度是O(n + C * n)。由于笛卡尔积的总组合数C通常远大于集合的数量n（比如示例中n=3，C=27），O(n)的部分可以忽略不计，最终时间复杂度简化为：

O(n * k₁ * k₂ * ... * kₙ)

举个实际例子：示例中输入3个各含3个元素的集合，总组合数是27，总操作数大概是3 + 27*3 = 84，和O(3*27)=O(81)的量级完全匹配。

内容的提问来源于stack exchange，提问作者mounika's diary