0

これは私が受講しているコースのオプションの質問であり、4nという答えを提供します。しかし、今、私がそれについてどれだけ考えても、彼らがどのようにしてこれに到達したのか理解できません。私はまだ非常に新しく、大きなO表記について学んでいるだけなので、単純なものが欠けていると確信していますが、それは私には意味がありません。私の考えでは、バブルソートにはn * kの演算が必要なので、kを2kにすると、n*2kになります。そして、最悪のシナリオk = n --1を信じているので、実際にはn * 2nAKA3nです。私はおそらくこれを完全に間違ってやっていますが、それが私が助けを求めてここにいる理由です。私のコースは実際にはこのような問題をカバーしていなかった（または感じなかった）ので、どのようにアプローチすればよいかわかりません。ありがとう！

4

1 に答える 1

0

バブルソートはBigOk ^ 2の複雑さであり、最悪の場合と平均の両方

したがって、サイズkに対してn個の操作があります。これは、k ^ 2=nであることを意味します。

したがって、kを2倍にすると、（2k）^ 2=Xまたは4k^2 = Xになります。ここで、X =2kサイズの操作の数

n = k ^ 2であるという事実をプラグインすると、4n=Xになります。

あなたの答えがあります:)

于 2013-02-22T17:44:37.393 に答える