理論的計算量の見積もりに関して - その2

1 の続き
前回、sorting は比較の回数を基準に計算量を見積もっているため、quicksort の最悪時である O(n^2) の比較回数があったとしても、実際には実行時間は極端に長くならない(むしろ短い)。

この swap 操作にかかる計算量が比較回数に比べが大きいという検証のために 2種類の BucketSort の実行結果を比べてみる。

・BucketSort1
データ領域は入力のものだけ。スワップを繰り返し行う。

・BucketSort2
一時的なデータ領域を確保し、スワップではなくデータ移動を繰り返し行う。

BucketSort1 : 22.2s
BucketSort2 : 1.3s

このように swap 操作をデータ移動に置き換えることで、22.2 / 1.3 ≒ 17 倍程の性能差が生じてしまう。