我正在寻找一个直观的，真实的问题的例子，这个问题需要(最坏的情况)指数时间复杂度来解决我的演讲。
下面是我想到的其他时间复杂性的例子(其中许多来自这个SO问题):
- O(1) -确定一个数字是奇数还是偶数
- O(log N) -在字典中查找单词(使用二进制搜索)
- O(N) -看书
- O(N log N) -排序一副纸牌(使用归并排序)
- O(N^2) -检查购物车中是否有购物清单上的所有东西
- 0(无限)-投掷硬币，直到它落在正面
任何想法?
- O(10^N):试图通过测试所有可能的组合来破解密码(假设长度为N的数字密码)
<罢工> 注。为什么你的最后一个例子的复杂性是0(无穷大)?它是线性搜索O(N)。世界上只有不到70亿人
一家披萨餐厅有多种配料可供选择
- 意大利辣香肠 椒>
- 菠萝(在你尝过之前不要敲它!)
顾客可以选择任何配料的组合，也可以什么配料都不加。现在考虑一种算法，它可以找到所有可能的唯一配料组合。这是一个时间复杂度为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万种可能的组合!
一个蛮力和朴素n皇后问题的解。
你必须在n*n的棋盘上放n个皇后，而且不能被别人取走。
while there are untried configs,
go to next solution and
test it
假设每个皇后都在给定的行上，则有n种可能放置皇后和n种(n-1)其他皇后(因为没有检查重复的行)。
所以复杂度是0 (n^n)
旅行商问题的蛮力解为O(n!)，近似于O(n ^ n)
如何在集合中找到整数的子集，使它们的和为指定值X?
我相信这是复杂度O(2^(n/2))