指数时间复杂度的现实例子

Question

我正在寻找一个直观的,现实世界的问题示例,该问题需要(最坏的情况)指数时间复杂度来解决我正在给出的谈话.

以下是我提出的其他时间复杂性的例子(其中许多来自这个SO问题):

• O(1) - 确定数字是奇数还是偶数
• O(log N) - 在字典中查找单词(使用二进制搜索)
• O(N) - 读一本书
• O(N log N) - 排序一副扑克牌(使用合并排序)
• O(N ^ 2) - 检查您的购物车上是否包含所有物品
• O(无穷大) - 掷硬币直到落在头上

有任何想法吗？

Answer 1

• O(10 ^ N):尝试通过测试每个可能的组合来破解密码(假设长度为N的数字密码)

ps为什么你的最后一个例子是复杂度O(无穷大)？它是线性搜索O(N)..世界上人口不到70亿.

Answer 2

披萨店有多种配料可供选择

• 意大利辣香肠
• 辣椒
• 菠萝（在你尝试之前不要敲它！）

顾客可以为他们的披萨选择任何配料的组合，或者根本不选择配料。现在考虑一种算法，该算法可以找到每种可能的独特配料组合。这是一个时间复杂度为 O(2^n) 的指数算法。

当您向菜单中添加新的配料时，看看可能的组合如何（呈指数级）增长：

0 toppings: 1 combination (no toppings at all)
1 toppings: 2 combinations (none, a)
2 toppings: 4 combinations (none, a, b, ab)
3 toppings: 8 combinations (none, a, b, c, ab, ac, bc, abc)
...
...
10 toppings: 1,024 combinations
20 toppings: 1,048,576 combinations

因此，只需 20 种配料，就有超过 100 万种可能的组合！