从k个各含n个元素的集合枚举组合的时间复杂度是否为多项式时间？

首先明确多项式时间的核心定义：多项式时间复杂度是指可以表示为O(n^c)的形式，其中c是固定不变的常数，与输入规模无关。

针对你的问题，需要分两种场景判断：

• 若k是固定常数（比如你的程序永远只处理3个集合，k=3不会变）：此时O(n^k)属于多项式时间，因为指数是固定常数，符合多项式时间的定义。
• 若k是输入的一部分（即你程序处理的集合数量k会随输入变化，比如这次输入5个集合，下次输入10个）：此时O(n^{k)属于**指数时间复杂度**，远差于多项式时间。这种情况下，k是输入规模的一部分，复杂度会随着k的增长呈爆炸式上升——虽然它比O(n}n)的增长速度略慢（当k<n时），但本质上都属于非多项式的难解范畴，一旦k变大，程序运行时间会急剧增加。

结合你的场景：程序输入是包含k个集合的集合，说明k是输入的变量，因此你的程序时间复杂度属于指数时间，而非多项式时间。

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