38

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

以下是我提出的其他时间复杂性的示例（其中许多来自这个 SO question）：

  • O(1) - 判断一个数是奇数还是偶数
  • O(log N) - 在字典中查找一个单词（使用二进制搜索）
  • O(N) - 看书
  • O(N log N) - 对一副扑克牌进行排序（使用归并排序）
  • O(N^2) - 检查你的手推车里是否有购物清单上的所有东西
  • O(infinity) - 掷硬币直到它落在正面

有任何想法吗？

4

5 回答 5

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

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

于 2011-08-14T07:55:15.607 回答
4

比萨餐厅有多种配料可供选择

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

顾客可以为他们的披萨选择任何配料组合或根本不选择配料。现在考虑一个算法，它可以找到所有可能的独特配料组合。这是一个时间复杂度为 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 万种可能的组合！

于 2020-06-14T11:34:06.537 回答
1

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

于 2011-08-14T07:54:48.863 回答
1

一个蛮力和幼稚的 n-queens 问题的解决方案。

您必须将 n 个皇后放在一个 *n 板上，而没有它们被其他人带走。

while there are untried configs, go to next solution and test it

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

因此，您的复杂度为 O(n^n)

于 2011-08-14T08:01:10.893 回答
1

在一个集合中找到一个整数子集，使得它们的总和是一个指定的值 X 怎么样？

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

于 2017-05-20T09:20:31.603 回答