バブルソートを使用して名前をソートするアルゴリズムの複雑さ

Question

バブルソートを使用して200の名前をソートするのに200秒かかりました。その後、800秒でどれくらいの名前がソートされますか。私がこれを解決するのを助けてください。私は、バブルソートの時間計算を使用してそれを解決しようとしたが、私はそれを

を行うことができませんし、またバブルソートの複雑さは最悪でO(n^2)で次のコード

int somefunct(int n) 
    { 
     if(n<=2) 
     return 1; 
     else 
     return (somefunct(floor(sqrt(x)))+x); 
    } 

Answer 1

の複雑さを見つけたいです場合。したがって、与えられた時間の4倍で現在の名前の2倍のソートを行います。すなわち、最悪の場合、800秒で400の名前。

Answer 2

最悪の場合にはバブルソートでソートする時間がnの学位2の多項式であるので、我々は持っている：

今

t = an^2 + bn + c

、nは（ここでは200）十分な大きさであるため、ので、我々は得るために、最後の2項を無視することができます：

t = an^2

値置く：a = 1/200

01得るために t = 200と n = 200を

したがって、800秒で、あなたが並べ替え[最大にできるようになります：これは最悪のシナリオであるため、

800 = (1/200)*(n^2)

=> n = 400名[最大

。

Answer 3

200の名前をソートする場合、バブルソートは200 * 199/2 = 19900の比較を行います。
1回の比較に必要な時間は200秒です。 800秒でそれは80,000の比較をすることができます。
n（n-1）/ 2 = 80,000となるようなnを見つける必要があります。 => n^2 - n = 160000。最後の項は無視することができます。したがって、n^2 = 160000。回答= 400。