ソートの用語
そうちゃんさん
(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種類あります。時間計算量と空間計算量。
時間計算量は、どれだけの時間がかかるかを表し、
空間計算量は、どれだけのメモリが必要かを表します。
オーダー(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日経過したスレッドへの投稿はできません。
広告