是什么让两个函数在大0符号中有根本不同的效率时间

今天我遇到了一个问题，要根据效率对几个函数进行排序，并用数学方法计算哪些函数具有相同的大0符号。长话短说，我最终与我的同学发生了分歧，即运行时间为2^n的函数与运行时间为n^(n/2)的函数之间是否存在根本区别。

我被告知，在大0符号中，当n接近无穷大时，前系数最终是微不足道的，因为它们只是同一个父函数的垂直缩放，当n很大时，6*n与n并没有那么大的不同，因为它们都有相同的父增长率，这是有道理的。我的论点是，因为这个函数的垂直缩放是微不足道的，因为它只是同一事物的子函数，任何常数变换将保留整个父函数，所以子函数将具有相同的基本增长率，并最终被简化为相同的符号(在这种情况下为O(2^n))。

我的同学指出

2^(n/2) = (2^(1/2))^n = sqrt(2)^n

…因为当n趋于无穷时，1.414^n比2^n小得多，所以它应该明显更大。

我的同学于是提出如果

两个函数有不同的大0符号

lim((f(n)'s efficiency)/(g(n)'s efficiency)) as n->infinity 
    is either infinity (f(n) is bigger), or 0 (g(n) is bigger)
And because ((2^n) / (2^(n/2))) = ((2^(n/2) * 2^(n/2)) / (2^(n/2))) = 
    2^(n/2), approaches infinity, they must have a rate of change that is
    fundamentally different.

我同学的理论是什么使得两种算法有不同的大O符号，这显然对线性vs线性，线性vs二次，以及几乎任何其他常见情况都有意义，但话又说回，我的也是如此。一个变换后的线性函数(意思是它被平移了或者被垂直或水平缩放了，但没有被负数，0，等等缩放)总是有一个大0符号O(n)因为它是线性的。任何二次函数最终都是O(n²)因为常数会变得不重要只有n²项会起作用，因为它是一个变换后的二次函数。(也适用于其他东西，你懂的)很明显，x^2从根本上不同于x^3，因为你不能缩放二次函数来匹配三次函数，所以它们必须足够不同，才能在Big-O中得到自己的类别。

显然[至少]我们中有一个人想错了。我的意思是，O(2^(n/2))要么化简为O(2^n)要么不化简，对吧?

那么，我们中的哪一个(如果有的话)是正确的，为什么另一个是错误的，最重要的是，在这种情况下，我们如何判断两个效率低下的人是否有根本的不同?

谢谢!

你最初的问题比较了2^n和n^(n/2)。很容易看出，n^(n/2)更慢，因为在n=4时，它们等于(16)，从这一点开始，n^(n/2)越来越大。

2^(n/2)比这两个都小。实际上，c是常数nc是n *常数，nc^c

相关内容

最新更新

热门标签：