假设我们有一个算法需要列出从n个元素中选择k个元素的所有可能性(k<=n(，特定算法的时间复杂度是指数级的吗？为什么？
No.
有 n 选择 k = n！/(k！(n-k(！可能性 [1]。
考虑一下，n 选择 k = n^k/(k！(。[2]。
假设你保持 k 不变，随着 n 的增长，多项式时间的可能性量会增加。
对于此示例，请忽略 (1/(k！(( 项，因为它是常量。如果 k = 2，并且您将 n 从 2 增加到 3，那么您有 2^2 到 3^2 的变化。指数变化将从 2^2 到 2^3。这是不一样的。
保持 k 恒定并改变 n 会导致 O(n^k( 的大 O(1/(k！( 项是常数，您忽略它(。
由于输入实例包含数字，因此需要仔细考虑输入实例的大小 - 对弱NP硬度的基本熟悉也会有所帮助。
假设我们修复k=1并以二进制方式对n进行编码。由于算法必须访问n choose 1 = n数字，因此至少需要n步骤。由于n的数量大小在输入大小(用于编码n的位数(上可能是指数级的，因此在最坏的情况下，算法会消耗指数时间。
您可以通过编写一个简单的 C 程序来感受这种指数时间行为，该程序使用 n = 2^64 打印从 1 到 n 的所有数字，并查看您在一分钟内走了多远。虽然输入只有 64 位长，但假设您的设备每秒可以打印一百万个数字，则打印所有数字大约需要 600 years。
一种从 n 个唯一元素 (k
<=n( 中找到选择 k 个元素的所有可能性的算法，它没有指数时间复杂度 O(K^n(，因为它具有阶乘时间复杂度 O(n！(。相关公式为：
p = n!/(k!(n-k)!)