- アシスタントマネージャー
- オフショアPJマネージャー
- 業務改善(BPR)
- 他76件の職種
-
開発
- オフショアPJマネージャー
- Webエンジニア
- エンジニアオープンポジション
- Javaエンジニア(楽楽明細)
- ブリッジSE(大阪)
- ブリッジSE/オフショア開発
- エンジニアリングマネージャ
- テックリード(大阪/PHP)
- プロジェクトマネージャー
- PM(楽楽シリーズ)
- Webエンジニア(大阪PHP)
- フロントエンドマネージャー候補
- フロントエンドエンジニア
- Webエンジニア
- フロントエンド(リーダー)
- Android/iOSアプリ
- 社内SE(大阪/セキュリティ)
- インフラエンジニア
- 社内SE(大阪/インフラ)
- インフラエンジニア/マネージャ
- インフラエンジニア
- 社内SE(データエンジニア)
- 戦略企画・データマネジメント
- データマネジメント・戦略企画
- AI/機械学習エンジニア
- QAリーダー/マネージャー
- システム企画
- 品質管理/技術支援チーム
- 社内SE(業務改善推進)
- UI/UXマネージャー
- UIデザイナー(リーダー)
- UIデザイナー
-
ビジネス
- アシスタントマネージャー
- PdM(楽楽シリーズ)
- 開発マネージャー
- PMMプロダクトマーケティング
- 導入支援/導入コンサルタント
- プロジェクトマネージャ(大阪)
- プロダクトセキュリティ
- プロダクトマネージャー(AI)
- プロダクトマネージャー
- ドメインエキスパート
- プロダクトマネージャー(UX)
- 経営企画/事業分析
- 経営企画
- データマネジメント・マーケ戦略
- 法務
- 内部監査(業務監査)
- セールスマネージャー
- 法人営業/カスタマーサクセス
- 営業企画オープンポジション
- 営業企画(イネーブルメント)
- ITセールス(広島)
- ITセールス(名古屋)
- フィールドセールス
- フィールドセールス(名古屋)
- フィールドセールス(法人営業)
- 法人営業
- フィールドセールス(東京)
- 営業企画(戦略立案)
- ITセールス
- ビジネスオープン
- ITセールス経験者
- ブランド企画
- CSマーケティング
- オンラインマーケティング
- マーケティング担当
- マーケティングリーダー
- オフラインマーケティング
- 営業推進リーダー(楽楽精算)
- 製品企画/プロダクトマーケ
- ブランド企画・ブランディング
- 製品企画/法要件(楽楽明細)
- 企画マーケティング
- その他
ソートアルゴリズムで見るプログラムの計算量
はじめに
はじめまして。開発エンジニアのCarboxyです。
ラクスに新卒で入社して、今年で3年目になります。
今回は、新卒(≒エンジニア初心者)が、効率の良いプログラムを書けるようになるきっかけになればと思い、プログラムの計算量の求め方とその比較方法をソートアルゴリズム(選択ソート)を例に紹介します。
計算量とは
ある問題を解くためにどのくらい計算が必要かどうか(どのくらい時間がかかるか)
→アルゴリズムの性能評価に使用できる。
O(オーダー)記法を用いて示す。
※計算量には時間計算量と空間計算量があるが、この記事では時間計算量の事を指す。
O(オーダ)記法
計算量の一般的な記述方法。大まかな時間計算量を表す。
例として、入力サイズ n の関数として表される時間計算量T(n)が
T(n)=10n2+100n+1000T(n)=10n2+100n+1000
で与えられる場合、オーダー記法では最も次数の高い項の係数を省いて
O(n2)O(n2)
となる。なぜこのように最も次数の高い項(主要項)の係数を省くような、漸近的な評価が使われるかというと、入力サイズ n が十分に大きい場合は、時間計算量は主要項にのみ依存するからである。
選択ソート
選択ソートを例に計算量を考える。
選択ソートは最も基本的なソートアルゴリズムの1つで、次のようなアイデアに基づきソートを行っていく。
1,入力データの中から最大のデータを見つける。
2,見つけた最大のデータをソートの対象から除外する。
3, 1と2 の操作を n - 1 回繰り返す。
入力サイズ n の配列 D[0]、D[1]、・・・、D[n-1]
このアルゴリズムは、2重のfor文により構成されている。変数 n に依存する i , j の2重ループなのだからO(n^2)になることは安易に想像できるが、計算すると次のようになる。
外側のfor文の繰り返し実行回数は n - 1 回であり、内側のfor文は外側のfor文の変数 i に依存し、i 回の繰り返しとなっている。したがって、このアルゴリズムの計算量は、以下の式で表される。
O(1)×∑i=1n−1iO(1)×∑i=1n−1i
=O(1)×{1+2+3+...+(n−1)}=O(1)×{1+2+3+...+(n−1)}
=O(1)×n(n−1)2=O(1)×n(n−1)2
=O(n2)=O(n2)
計算量の比較
複雑になるため詳細は省略するが、その他のソートアルゴリズムの計算量を計算すると、例えばクイックソートの場合はO(n logn)になる。オーダー記法の漸近的な大小関係は以下のようになることから、選択ソートとクイックソートを比較するとクイックソートのほうが計算量が小さい事が数値的にわかる。
logn<n−−√<n<nlogn<n2<n3<...<2n<n!logn<n<n<nlogn<n2<n3<...<2n<n!
まとめ
オーダ記法によって漸近的な時間計算量を示すことができる。
プログラムを実行して時間を測定しなくとも、入力サイズ n に対してどのアルゴリズムが一番速いか数値的に比較できる。