我想问是否有人能回答这些问题,并检查我的解决方案。我真的没有得到这些函数的Big-O。
e(n(=n!+2^n
f(n(=log10(n(*n/2+n
g(n(=n2+n*log(n(
h(n(=2^30n*4^log2(n(
我想:
e(n(n!因为n!呈指数级增长。
f(n(n(log(n,但我真的不知道为什么
g(n(n^2
h(n(n
如果有任何答案,我将不胜感激。谢谢
Big O表示法允许我们评估函数在趋向无穷大时相对于某个量的增长。
函数的大O表示法是它增长最快的组成部分的表示法。大O表示法限制了函数的增长。
例如,如果一个函数被称为O(n(。存在一些k使得f(n(<=k*n表示所有n。
当我们看到趋向无穷大的值时,我们忽略了方程的所有其他组成部分。当n趋于无穷大时,方程的其他组成部分被淹没了。
当我们描述函数的一般关系时,我们忽略任何常数,因为它趋向于某个值。常数使事情更难分析。
-
e(n(=n!+2^n。阶乘是方程中增长最快的成分,所以大O表示法是O(n!(。
-
f(n(=log10(n(*n/2+n。快速增长的成分是log10(n(*n/2。我们说大O表示法是O(nlogn(。我们使用什么样的对数基数并不重要,因为我们可以通过使用常数因子在对数基数之间进行转换。
-
g(n(=n^2+n*log(n(。大O表示法是n^2。这是因为相对于n,n^2的增长速度快于n*log(n(。
-
h(n(=(2^30(*n*4^log2(n(。时间复杂度为O(nlogn(。这个方程中的常数是2^30和4,所以我们忽略这些值。当这样做的时候,你可以清楚地看到时间复杂度是O(nlogn(。