3^n和2^n之间不是一个常数啊，难道不是1.5^n吗？

Answer 1

liuyubobobo 2018-02-25 09:33:40

由于这个课程不涉及非常严谨的复杂度计算，所以在这里我的用语可能不够严谨。抱歉。

在这里，我是指，二者都是指数级的复杂度。具体是指：

2^n = (3^(log3(2)))^n = 3^(log3(2)*n)

这里，log3(2)是指对2求以3为底的对数。

所以2^n和3^n都可以表达成2^(cn)的形式，其中c是常数。所以通常说二者都是指数级复杂度，相差一个常数，这个常数就是c。在上面的例子里，c = log3(2)。

不过从严格的复杂度定义的角度，确实：2^n != Big-Theta(3^n)；他们之间的关系是：

2^n = Big-O(3^n)

3^n = Big-Omega(2^n)

如果对Big-O，Big-Theta，Big-Omega这些符号的严格数学定义感兴趣，可以在网上搜索相应的资料，或者看算法导论第三章，介绍的非常清楚。不过通常在面试中不会考察这么严谨的复杂度计算方法，习惯上把指数级复杂度归为一类。即O(a^n)的形式。

• 奋斗一会儿 #1

  老师，感觉2^n = (3^(log3(2)))^n = 3^(log3(2)*n)是不是应该写成3^n = (2^(log2(3)))^n =2^(log2(3)*n)。不过写成那样也明白是啥意思。