是什么让两个函数在大 O 表示法中具有根本不同的效率时间
What makes two functions have fundamentally different efficiency times in Big O notation
今天我遇到了一个问题，即根据效率对多个函数进行排序，并以数学方式计算哪些函数具有相同的大 O 表示法。长话短说，我最终与我的同学就 运行 时间为 2^n 的函数与 运行 时间为n^(n/2).
有人告诉我，在 Big O 表示法中，当 n 接近无穷大时，前导系数最终变得微不足道，因为它们只是同一父函数的垂直缩放，当 n 很大时，6*n 并不是真的与 n 不同，因为它们都有相同的父级增长率，这是有道理的。我的论点是因为函数的这种垂直缩放是微不足道的，因为它只是同一事物的子函数，所以进行的任何恒定转换都会保留整个父函数，因此子函数将具有相同的基本增长率并最终成为简化为相同的符号（在本例中为 O(2^n)）。
我的同学指出
2^(n/2) = (2^(1/2))^n = sqrt(2)^n
...并且因为 1.414^n 比 2^n 小得多，因为 n 接近无穷大，所以它应该明显更大。
然后我的同学提出两个函数有不同的大O表示法如果
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 表示法的理论显然对线性与线性、线性与二次以及几乎任何其他常见情况都有意义，但话又说回来，我的也是如此。变换后的线性函数（意味着它被垂直或水平平移和/或缩放，但不按负数、零等缩放）将始终具有 O(n) 的大 O 表示法，因为它是线性的。任何二次函数最终都会成为 O(n^2)，因为常数将变得无关紧要，只有 n^2 项才是重要的，因为它是一个变换的二次函数。 （也适用于其他东西，你明白了）显然，x^2 与 x^3 根本不同，因为你不能缩放二次函数来匹配三次函数，所以它们必须足够不同才能在 Big- O.
很明显，[至少]我们中的一个人以错误的方式思考这个问题。我的意思是，要么 O(2^(n/2)) 被简化为 O(2^n) 要么没有，对吧？
那么我们中哪一个（如果有的话）是对的，为什么另一个是错的，最重要的是，在这种情况下，我们如何判断两种低效率是否有根本不同？
谢谢！
你最初的问题是比较 2^n 和 n^(n/2)。很容易看出 n^(n/2) 比 n^(n/2) 慢，因为在 n=4 时它们相等 (16)，并且从那时起 n^(n/2) 越来越大。
2^(n/2) 比这两个都小。实际上，其中 c 是常数，nc 是 n * 常数，nc^c < c^nc < nc^nc.
在2^n vs 2^(n/2)的情况下，2^n有一个更大的O，因为没有常数可以使2^(n/2)跟上它作为n增加。
今天我遇到了一个问题，即根据效率对多个函数进行排序，并以数学方式计算哪些函数具有相同的大 O 表示法。长话短说，我最终与我的同学就 运行 时间为 2^n 的函数与 运行 时间为n^(n/2).
有人告诉我，在 Big O 表示法中，当 n 接近无穷大时，前导系数最终变得微不足道，因为它们只是同一父函数的垂直缩放，当 n 很大时，6*n 并不是真的与 n 不同，因为它们都有相同的父级增长率，这是有道理的。我的论点是因为函数的这种垂直缩放是微不足道的，因为它只是同一事物的子函数，所以进行的任何恒定转换都会保留整个父函数，因此子函数将具有相同的基本增长率并最终成为简化为相同的符号（在本例中为 O(2^n)）。
我的同学指出
2^(n/2) = (2^(1/2))^n = sqrt(2)^n
...并且因为 1.414^n 比 2^n 小得多，因为 n 接近无穷大，所以它应该明显更大。
然后我的同学提出两个函数有不同的大O表示法如果
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 表示法的理论显然对线性与线性、线性与二次以及几乎任何其他常见情况都有意义，但话又说回来，我的也是如此。变换后的线性函数（意味着它被垂直或水平平移和/或缩放，但不按负数、零等缩放）将始终具有 O(n) 的大 O 表示法，因为它是线性的。任何二次函数最终都会成为 O(n^2)，因为常数将变得无关紧要，只有 n^2 项才是重要的，因为它是一个变换的二次函数。 （也适用于其他东西，你明白了）显然，x^2 与 x^3 根本不同，因为你不能缩放二次函数来匹配三次函数，所以它们必须足够不同才能在 Big- O.
很明显，[至少]我们中的一个人以错误的方式思考这个问题。我的意思是，要么 O(2^(n/2)) 被简化为 O(2^n) 要么没有，对吧？
那么我们中哪一个（如果有的话）是对的，为什么另一个是错的，最重要的是，在这种情况下，我们如何判断两种低效率是否有根本不同？
谢谢！
你最初的问题是比较 2^n 和 n^(n/2)。很容易看出 n^(n/2) 比 n^(n/2) 慢，因为在 n=4 时它们相等 (16)，并且从那时起 n^(n/2) 越来越大。
2^(n/2) 比这两个都小。实际上，其中 c 是常数，nc 是 n * 常数，nc^c < c^nc < nc^nc.
在2^n vs 2^(n/2)的情况下，2^n有一个更大的O，因为没有常数可以使2^(n/2)跟上它作为n增加。