#author("2020-08-10T12:22:47+00:00","","")
#author("2020-08-11T03:44:51+00:00","","")
*プログラミング系 [#e3f5ea3d]

#contents
-[[back>ikeue2019/study]]

**問題&答え [#qce11870]
-編集中
#br

**計算量 [#g18a9681]
-プログラムにおいて、入力から出力を得るまでの「時間」について考える。
-入力の数nに対し、出力が得られるまでの時間をnの関数で表したf(n)を''時間計算量''という。~
プログラムにおける計算量には、時間計算量以外にも様々なものがある。
|時間計算量|サイズnの入力に対して出力が得られるまでの時間を表す関数f(n)|
|空間計算量|時間計算量の時間を「メモリ」に置き換えて考えて表したもの|
|平均計算量|全ての入力パターンに対し、それらの計算量を平均をとったもの|
|最大計算量|そのアルゴリズムにとって最悪のデータを使った場合の計算量|
#br

***オーダー [#o19a6d3b]
-ある関数g(n)と2つの定数c,n0が存在し、n>n0であるnについて、~
f(n) < cg(n)~
が常に成り立つとき、f(n)=O(g(n))と記し、「計算量は''オーダーg(n)''である」という。~
(十分大きなnに対しては、計算量f(n)はg(n)の定数倍である)
--例. f(n) = 2n~2 + n +5である場合のオーダー~
計算量は''O(n~2)''である。~
nが十分大きいとき、f(n) ≦ 3×n~2が常に成り立つ。
#br

**整列アルゴリズム一覧 [#c6d67f48]
|名称|処理内容|計算量|
|バブルソート|配列の先頭から後ろに向かってスキャンし、隣り合う要素の大小関係が逆である場合は入れ替える整列アルゴリズム。|O(n^2)|
|選択ソート|未整列の(整列されていない)部分から最小の要素を選び、それを未整列部分の先頭に移動させ、徐々に整列を行っていく整列アルゴリズム。|O(n^2)|
|挿入ソート|配列の一部を整列済みとし、残りの要素を一つずつ、整列済みの部分の適切な位置に挿入していく整列アルゴリズム。|O(n^2)|
|バブルソート|配列の先頭から後ろに向かってスキャンし、隣り合う要素の大小関係が逆である場合は入れ替える。|O(n^2)|
|選択ソート|未整列の(整列されていない)部分から最小の要素を選び、それを未整列部分の先頭に移動させ、徐々に整列を行っていく。|O(n^2)|
|挿入ソート|配列の一部を整列済みとし、残りの要素を一つずつ、整列済みの部分の適切な位置に挿入していく。|O(n^2)|
|ヒープソート|insert処理によって探索木を構築し、それに対してremoveMin処理を行っていき、要素を取り出していくことで整列を行う。|O(nlogn) |
|マージソート|データ列を真ん中で半分に分けていき、それぞれの部分列で整列を行った後に合併(マージ)を行っていくことで整列を行う。|O(nlogn)|
|シェルソート|hずつ離れた要素同士で整列を行っていき、hを大きい値から小さい値に変化させてこの処理を繰り返すことで整列を行う。|O(n^1.5)程度|
|クイックソート|1つの要素を枢軸として定め、枢軸より小さい要素を左側に、大きい要素を右側に集める処理を繰り返すことによって整列を行う。|O(nlogn)。|
#br


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS