渐近复杂度

-3

假设计算机在微秒内执行一条指令，并且已知算法具有O（2^n）的复杂度，如果给该算法提供最多12小时的计算机时间，则确定最大可能可以使用该算法的n的值渐近复杂度

2010-09-20 Fiona

这没有意义。 O（2^n）可能意味着只有2^n，但它也可能意味着1000000000 * 2^n。 – Henrik 2010-09-20 14:40:33

如果包括N的运行时间是4小时......如果在较短的运行时间内没有较低顺序的条件，则可以做出明智的决定。简而言之，这个问题被打破*和*很难解决。 – dmckee 2010-09-20 14:43:47

这听起来很像作业。另外，请使用标点和大写。 – 2010-09-20 14:49:40

不可以。

O(2^n)意味着存在C使得limit n->infinity f(n)<=C*(2^n)。
但是这个C也可以是023945290378569237845692378456923847569283475635463463456的数量，所以即使是12小时也不能确保它即使在小输入时也能运行。

来源

2010-09-20 14:44:56

因此，最小的可能值显然是0. :) – Vatine 2010-09-20 14:50:28

@Vatine不一定，因为只有极限可以保证，即使这可能需要14个小时。 – cobbal 2010-09-20 14:53:55

信息不足。一个O（2^n）的算法不一定需要大小为n的输入2^n步，它可能需要一个常数因子。事实上，它可能需要C *（2^n）+ B操作，其中C和B是常量（即它们不依赖于n），它们都是整数，并且C> = 1且B> = 0

来源

2010-09-20 14:51:25 ktho

那么，由于O（2^n）是一个指数复杂度，你被要求提供“最大可能的指数”，所以你试图找到一个N，所以2^N小于或等于12小时（* 3600秒，* 1000000微秒）。从那里，你可以使用对数来找到正确的值，或者估计一个初始N并迭代，直到找到一个值。

来源

2010-09-20 14:51:26 Vatine

回答

相关问题