複数の関数のビッグO表記

Question

複数の関数を使用している場合、大きなO表記に関する質問があります。

heap sort array of size n 
for i = 1 to n{ 
    retrieve array[i] 
    change value of array[i] 
} 

私は、ヒープの並べ替えを使用して（N）（ログ）Oであることを知っている： は、私は時間の複雑さは、以下の擬似コードのために何であるかを知りたいとしましょう。配列内のデータの取得と変更はO（1）なので、ループは複雑さO（n）です。 私の質問は、このコード全体の複雑さは？それは単なる時間の複雑さの最大のものですか？この場合、O（n log（n））？事前に

for i = 1 to n{ 
    // nothing fancy here 
} 
for y = 1 to n{ 
    // nothing fancy here either 
} 

ありがとう： もしそうなら、何がこのようになります機能の複雑さになります。

Answer 1

Big-O表記は、n（入力サイズ）が無限に近づいていることを支配しています。したがって、コードAとBの2つのチャンクが連続して実行される場合、全体の時間動作はO（A）とO（B）のうち大きい方になります。あなたのケースでは

ヒープソートがO(nlogn)アルゴリズムであり、ループは、単にO(n)アルゴリズムであれば、その後、nが無限大に近づくようnlognは最終的に道大きくなりますので、それは重要な項のみです。 あなたの全体の時間行動はO(nlogn)です。

もちろんこれはすべての理論です。実世界では、ループの中で（I/Oのように）ループが遅いものを実行する場合は、nがループよりも遅くなる前に、巨大になる可能性があります。

Answer 2

for i = 1 to n{ 
    // nothing fancy here 
} //O(n) 

for y = 1 to n{ 
    // nothing fancy here 
} //O(n) 

したがって、一緒にO(n) + O(n) = O(n)です。