渐进复杂性
假设计算机在一微秒内执行一条指令，并且已知算法的复杂度为 O(2^n)，如果为该算法提供最多 12 小时的计算机时间，请确定 n 的最大可能值，其中该算法可以使用
suppose a computer executes one instruction in a microsecond and an algorithm is known to have a complexity of O(2^n), if a maximum of 12 hours of computer time is given to this algorithm, determine the largest possible value of n for which the algorithm can be used
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
好吧，由于 O(2^n) 是指数复杂度，并且要求您提供“最大可能的指数”，因此您试图找到 N，以便 2^N 小于或等于 12 小时 (* 3600 秒，* 1000000 微秒）。从那里，您可以使用对数来找到正确的值，或者估计初始 N 并迭代直到找到一个值。
Well, as O(2^n) is an exponential complexity and you're asked for the "largest possible exponent", you're trying to find an N, so that 2^N is less than or equal to 12 hours (* 3600 seconds, * 1000000 for the microseconds). From there, you can either use logarithms to find the right value or estimate an initial N and iterate until you find a value.
信息不足。对于大小为 n 的输入，O(2^n) 的算法不一定需要精确地执行 2^n 个步骤，它可能需要其常数因子。事实上，它可能需要 C*(2^n)+B 运算，其中 C 和 B 是常数（即，它们不依赖于 n），它们都是整数，并且 C >= 1 和 B >= 0。
Insufficient information. An algorithm that is O(2^n) doesn't necessarily take exactly 2^n steps for input of size n, it could take a constant factor of that. In fact, it could take C*(2^n)+B operations, where C and B are constant (that is, they don't depend on n), they are are both integers, and C >= 1 and B >= 0.
没有可以做的。
O(2^n)表示存在C使得limit n->infinity f(n)<=C*(2^n)。但是这个
C也可以是023945290378569237845692378456923847569283475635463463456的数字，所以即使12小时也不能保证它即使在很小的输入下也能运行。No can do.
O(2^n)means that there existsCsuch thatlimit n->infinity f(n)<=C*(2^n).But this
Ccan also be the number of023945290378569237845692378456923847569283475635463463456so even 12 hours cannot ensure that it will run even on small input.