在这个例子中：http ://www.wolframalpha.com/input/?i=2%5E%281000000000%2F2%29+%3C+%283%2F2%29%5E1000000000
我注意到无论你进入多高，这两个方程都非常相似n。是否所有具有常数的算法都n属于同一时间复杂度类别？如2^n、3^n、4^n等。
问问题
90 次
2 回答
2
它们属于同一类别，这并不意味着它们的复杂性相同。它们是指数运行时间算法。显然 2^n < 4^n
我们可以看到4^n/2^n = 2^2n/2^n = 2^n
这意味着4^n算法指数比 is 慢（倍2^n）2^n
同样的事情发生。但这并不意味着 2^n 远小于 4^n，它仍然是指数的，当 n>50 时将不可行。3^n1.5^n
请注意，这是因为 n 不在基数中。如果它们像这样在基数中：4n^k vs n^k 那么这两种算法是渐近相同的（只要 n 比实际数据大小相对小）。它们会在线性时间上有所不同，就像O(n) vs c * O(n)
于 2013-09-23T01:34:04.620 回答
1
如果 1 < a < b ，则时间复杂度 O(a n ) 和 O(b n )不同。作为一个快速证明，我们可以使用 big-O 符号的正式定义来证明 b n ≠ O(a n )。
这是矛盾的。假设 b n = O(a n ) 并且 1 < a < b。那么一定有一些 c 和 n 0使得对于任何 n ≥ n 0，我们有 b n ≤ c · a n。这意味着对于任何 n ≥ n 0 ， b n / a n ≤ c 。由于 b > a，应该开始清楚这是不可能的 - 随着 n 变大，b n / a n = (b / a) n将变得越来越大。特别是，如果我们选择任何 n ≥ n 0使得 n > log b / a c，那么我们将有
(b / a) n > (b / a) log(b/a) c = c
所以，如果我们选择 n = max{n 0 , c + 1}，那么 b n ≤ c · a n是不正确的，这与我们的假设 b n = O(a n ) 相矛盾。
这尤其意味着 O(2 n ) ≠ O(1.5 n ) 和 O(3 n ) ≠ O(2 n )。这就是为什么在使用大 O 表示法时，仍然需要指定最终使用的任何指数的底数。
还有一件事需要注意 - 虽然看起来 2 1000000000/2大约是 1.4 1000000000/2，但请注意这些是完全不同的数字。第一个是 10 10 8.1 ish 的形式，第二个是 10 10 8.2ish 的形式。这可能看起来差别不大，但绝对是巨大的。以 10 10 1和 10 10 2为例。第一个数字是 10 10，即 100 亿，需要十位数字才能写出。第二个是 10 100，一个googol，需要100个数字才能写出来。它们之间有很大的不同——第一个接近世界人口，而第二个大约是宇宙中的原子总数！
希望这可以帮助！
于 2013-09-23T01:34:07.793 回答