アルゴリズムの実行時間を関数F（x）=√n+（logn）^ 2として表すことができる場合

Question

アルゴリズムの実行時間を関数F(x)=√n+(logn)^2として表すことができる場合、ランニングタイム？

1. O(n) 
2. O(√n) 
3. O(log(n)^2) 
4. Omega(1) 

Answer 1

アルゴリズムの時間計算量は、複数の条件（ここでは√nと(log n)^2）で構成されている場合、あなたは大規模なnの最大取得する以外のすべての用語を無視することができます。

この場合、十分に大きいnの場合、√n >>(log n)^2であることが示されます。したがって、複雑さはO(√n)です。これは、あなたが質問に答えるのに十分な情報を提供するはずです。

nは実際には2番目の項が無視されるまで非常にを得る必要があるため、これは少し特殊なケースです。したがって、Big-Oの複雑さは理論的な記述を行い、は必ずしもではないことに注意する必要があります。