#author("2020-08-10T12:22:47+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)|
#br

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