基本的な質問ですみません。

ココさん  
(No.1)
選択法という整列のアルゴリズムについて教えてください。 
データが5個の場合、4回、3回、2回、1回と比較が行われ、
データの比較回数が10回で、n(n+1)÷2で表現されるのですが、どうしてこの数式になるのかが分かりません。等差数列とか、決まりきった公式のようなものなんでしょうか?
2019.05.12 15:18
ココさん  
(No.2)
追加で質問です、選択法の比較回数は「n(n+1)÷2」ですとあるのですが、最終的にはO(n2乗)になるというのも、どうしてそうなるのかが、分かりません・・・・
2019.05.12 15:29
yuさん 
(No.3)
選択ソートでは、最初はデータの位置を確定するために(n-1)回の比較が必要です。
次は、(n-2)回の比較、その次は(n-3)回の比較が必要となります。
これを繰り返すことになるので、(n-1)+(n-2)+(n-3)+...1  つまり、1からn-1までの総和を求めています。
n-1
Σ i = 1/2(n^2-n)=n(n+1)÷2
I=1

結果、計算量はO(n^2)になります。
簡単に言えば、入力によらずn^2に比例した計算量になります。
2019.05.12 21:05
ココさん  
(No.4)
>結果、計算量はO(n^2)になります。
>簡単に言えば、入力によらずn^2に比例した計算量になります。

ご回答ありがとうございます。
上記の内容にn=5で考えると、5^2=25回の判定を行うことになりますか?
選択法だと、4+3+2+1=10回ですよね?
ここの部分について教えてもらえませんでしょうか?
2019.05.12 22:40
ココさん  
(No.5)
質問していて、なんとなく感じたのですが、
Oの計算量はソートによってデータが移動する回数のことを指してるということでしょうか?
よくわかってなくて、本当にすみません。
教えてください。
2019.05.12 22:55
plさん 
(No.6)
等差数列は、連続する整数の和を求めるための数学的手法です。
n=5であるとき、教科書では10回なのに代入すると15回になるのは、あくまで等差数列的に求められることを示したかったとか、その程度ではないでしょうか。
ちなみに私の持っている教材にはn(n-1)/2とあり、質問者様の予想と同じ式になっています。これらはO的な発想では同じことです。
オーダ(なんとオーダーOrderのこと)では、1回も100回も同じことです。1万回でも1億回でも、それが整数値で無限でなければコンピュータにとって些細な事だからです。極端な例では些細ではなくなりますが、そういう話で実際的に使われることはないので問題ありません。
プログラミング的に言ってしまえば、ループ変数を2個使うから2次式で求められて、それ以外の項はオーダ的に無視されるよね。
つまり、まず1を2-5まで比較する必要があります。これは4回ですが、40回でも4万回でも=n回です。
次に、1は確定なので、2を3-5まで比較する必要があります。これは3回ですが=n回です。
n回比較する作業を、何回すれば良いでしょうか。
n-1回なので、それはn回に等しいです。
n回の比較をn回繰り返すから、n^2。これがオーダになります。
ちなみにn^2+nの場合、n^2以外の項は無視されます。これはn^2にとってnが些細過ぎる数だからです。
2019.05.13 06:37
助け人さん 
AP ゴールドマイスター
(No.7)
n(n+1)/2とn(n-1)/2が入り乱れているようです。

1からnまでの数の合計は、n(n+1)/2  nに5を代入すると15
1からn-1までの数の合計は、n(n-1)/2  nに5を代入すると10

n個の要素の選択ソートの比較回数は、(n-1)+(n-2)+・・・+2+1=n(n-1)/2
2019.05.13 07:25
yuさん 
(No.8)
下記の式でn(n+1)÷2と書いていましたが、n(n-1)÷2ですね。
n-1
Σ i = 1/2(n^2-n)=n(n-1)÷2
I=1

n=5で考えると、5*(5-1)*1/2=10です。

O(n)とは計算量のオーダーのことで、アルゴリズムへの入力サイズをnとして計算量がnに応じてどのように変化するか
ということです。
データが移動する回数というより、処理数(計算のステップ数)ですね。

2019.05.13 17:09
ココさん  
(No.9)
plさん、助け人さん、yuさんへ

いろんなモヤモヤが解消しました。
また、別のテーマで質問する機会があると思います。また、よろしくお願いします。
2019.05.14 07:40

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop