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

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

以下是我提出的其他时间复杂度的示例（其中许多取自这个问题 https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities):

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

有任何想法吗？

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

p.s.为什么你的最后一个例子的复杂度是 O(infinity) ？这是线性搜索 O(N) .. 世界上的人口不到 70 亿。