複数の複雑度

-1

私はアルゴリズムの一部に複雑さbig-O（nlogn）があり、その一部に複雑さbig-O（n）がある場合。アルゴリズムの最終的な複雑さは何でしょうか？私が知っている限り、それは大きなO（nlogn）になるでしょう。複数の複雑度

出典

2016-08-06 Barry S

アルゴリズムは何ですか？私たちから重要なものを隠さないようにしてください。 – HuStmpHrrr

あなたのケースでは（nlog（n））の何が重要かが考えられます。

それはあなたが「それの一部」によって何を意味するかに依存し

出典

2016-08-06 14:20:28

あなたが気にしないなら、私はこれに関するフォローアップの質問をしましたか？私は複雑さO（nlogn）とO（n^2）を持つアルゴリズムを実行するアルゴリズムを持っています。私はそれらを5000のサンプルで実行し、各サンプルにかかる時間をプロットしました。私が奇妙に思ったのは、サンプルサイズが大きくなるにつれて、O（n^2）がO（nlogn）よりも速くなったということです。これが起こることができますか、時間の複雑さが間違っている可能性がありますか？ –

いいえ、私はそれが可能だと思う、あなた自身のために見るために関数のグラフを比較することができます、水平軸はあなたがチェックし、垂直はcurrespondimg入力の実行時になります入力されます。 –

...

あなたはO（n）とO（LOGN）のバイナリ検索の複雑さを持つforループを持っていると仮定しましょう

あなたはこのように見えるプログラムする場合：

for(int i=0; i < n; i++) { // O(n) 
/// some stuff here 
} 
binarySearch(); // O(logn)

時間複雑さはO（n）は

ハウだろう版の場合には、このような状況を持っている：アルゴリズムは、アルゴリズムの時間の複雑さ、その後、別の時間の複雑さと異なるブロックで構成されている場合

：

for(int i=0; i < n; i++){ // O(n) 
    binarySearch(); // O(n * logn) 
}

時間複雑さはO（nlogn）

編集だろう= max（O（ブロック1）、O（ブロック2）、...）

出典

2016-08-06 14:23:02 CMPS

私は実際には非常に似通った状況です。複雑なO（n）のループとO（nlogn）の一種です。しかし、ソートはループとは独立して発生します。 –

@BarryS編集を確認する – CMPS

答えて

関連する問題