指数时间复杂度的真实示例

Question

我正在寻找一个直观的、现实世界的问题示例，该问题需要（最坏情况）指数时间复杂度来解决我正在做的演讲。

以下是我提出的其他时间复杂度的示例（其中许多取自 这个问题）：

• O(1) - 确定一个数字是奇数还是偶数
• O(log N) - 在字典中查找一个单词（使用二分搜索）
• O(N) - 读一本书
• O(N log N) - 对一副扑克牌进行排序（使用合并排序）
• O(N^2) - 检查购物车中是否有购物清单上的所有物品
• O(infinity) -抛硬币直到正面朝上

有什么想法吗？

Answer 1

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

ps 为什么你的最后一个例子的复杂度是 O(infinity) ？这是线性搜索 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 万种可能的组合！

Answer 3

一个暴力且幼稚的 n 皇后问题的解决方案。

你必须将 n 个皇后放在一个*n 个棋盘上，而不让它们被其他人拿走。

虽然有未尝试过的配置，
转到下一个解决方案并
测试一下

假设每个皇后都在给定的行上，则放置该皇后的可能性有 n 种，放置其他 (n-1) 个皇后的可能性也有 n 种（因为不检查重复的行）。

因此，你的复杂度是 O(n^n)

Answer 4

旅行商问题的强力解决方案是 O(n!)，大约为 O(N^N)

Answer 5

如何在集合中找到整数的子集，使其总和为指定值 X？

我相信这有复杂度 O(2^(n/2))