大O记数代数 [英] Big O notation algebra

问题描述

关于使用大O表示法的一些代数，我有几个问题:

I have a couple of questions regarding some algebra using big O notation:

如果f(n)=O(g(n))

是log(f(n)) = O(log(g(n)))吗?

是N^{f(n)}=O(N^{g(n)})吗? (其中N是任何实数)

is N^{f(n)}=O(N^{g(n)})? (where N is any real number)

推荐答案

• 是log(f(n)) = O(log(g(n)))吗?不，不是必须的，例如:

  • Is log(f(n)) = O(log(g(n))) ? No, it is not essential, for example:

    f(n)= n和g(n) = n^2.在这里f(n) = O(g(n))

    是N^{f(n)}=O(N^{g(n)})吗?不，这不是

    对于两种算法，比率可能保持恒定，但是每种算法提高到一定功率的比率将永远不会恒定.

    for two algorithms , the ratio may remain constant, but the ratio of each raised to certain power will never be constant.

    参加

    f ( ñ )= 2 ñ 和 G ( ñ )= ñ

    f ( n ) = 2 n and g ( n ) = n .

    2n确实是O(n).但是请考虑

    此限制不受限制-随着n变为无穷大，它变为无穷大.因此，

    This limit is not bounded - it goes to infinity as n goes to infinity. So,

    2^2n不是O(2n)，即2f(n)不是O(2g(n)).

    这篇关于大O记数代数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！