ソートの用語

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
そうちゃんさん  
(No.1)
ソートの用語で、「比較回数」と「計算量(オーダー」の違いとは何でしょう?
2016.02.15 20:39
がつくんさん 
(No.2)
まず、計算量(=オーダー)ではありません。
オーダー(O記法)とは、
あるNが存在して、
N < n のとき f(n) <= c * g(n)
であるとき(cは定数、f,gは関数)
f(n) = O(g(n))
と書きます。以下が使用例です。
3*n^2 + n + 5 = O(n^2)

つまり、O記法とはただの書き方なのです。
なので、比較回数もO記法で書くことができます。
例えば、n個のデータに対して、
バブルソートの比較回数は、O(n^2)です。
移動回数も、O(n^2)です。
ソートは基本的に比較と移動からなるので、
アバウトに考えて、計算量=比較回数+移動回数です。
なので、バブルソートの計算量は、O(n^2)となります。

次に、選択ソート。比較回数は、O(n^2)で、移動回数はO(n)です。
なので、計算量はO(n^2)となります。

ソートの場合においては、主に比較回数が計算量に影響してくるので、
両方をO記法で表すと、一致すると思います。

以下は、余談です。
また、計算量には主に2種類あります。時間計算量と空間計算量。
時間計算量は、どれだけの時間がかかるかを表し、
空間計算量は、どれだけのメモリが必要かを表します。
2016.02.15 21:35

返信投稿用フォーム

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

その他のスレッド


Pagetop