Big-O表示法因其定义而忽略常量因子(标量):
f(n)= O(g(n))iff存在自然数n 0和实数c,使得对于任何自然数n> n 0,| f(n)| ≤| cg(n)|
所以现在假设f(n)= O(k×g(n)).这意味着存在一些自然数n 0和实数c,使得对于任何n> n 0,我们得到| f(n)| ≤| c×k×g(n)|.
我们将用它来表明f(n)= O(g(n)).为此,请选择n 0作为自然数,将c×k作为实数.然后对于任何n> n 0,我们得到| f(n)| ≤|(c×k)×g(n)|,因此f(n)= O(g(n)).
希望这可以帮助!