指数时间复杂度的真实示例 [英] Real-world example of exponential time complexity

问题描述

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

I'm looking for an intuitive, real-world example of a problem that takes (worst case) exponential time complexity to solve for a talk I am giving.

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

Here are examples for other time complexities I have come up with (many of them taken from this SO question):

• O（1）-确定如果数字是奇数或偶数


• O（log N）-在字典中查找单词（使用二进制搜索）


• O（N） -读一本书


• O（N log N）-排序一副扑克牌（使用合并排序）


• O（N ^ 2） -检查购物车中是否有购物清单上的所有物品


• O（infinity）-扔硬币直到其落在头上

• O(1) - determining if a number is odd or even
• O(log N) - finding a word in the dictionary (using binary search)
• O(N) - reading a book
• O(N log N) - sorting a deck of playing cards (using merge sort)
• O(N^2) - checking if you have everything on your shopping list in your trolley
• O(infinity) - tossing a coin until it lands on heads

有什么想法吗？

推荐答案

• O（10 ^ N ）：尝试通过测试所有可能的组合来破坏密码ion（假设数字密码的长度为N）



ps 复杂度O（无穷大）它是线性搜索O（N）..世界上不到70亿人。

p.s. why is your last example is of complexity O(infinity) ? it's linear search O(N) .. there are less than 7 billion people in the world.

这篇关于指数时间复杂度的真实示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！