ikeue2019/study/Programing
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
*プログラミング系 [#e3f5ea3d]
#contents
-[[back>ikeue2019/study]]
**問題&答え [#qce11870]
-編集中
#br
**計算量 [#g18a9681]
-プログラムにおいて、入力から出力を得るまでの「時間」につ...
-入力の数nに対し、出力が得られるまでの時間をnの関数で表し...
プログラムにおける計算量には、時間計算量以外にも様々なも...
|時間計算量|サイズnの入力に対して出力が得られるまでの時間...
|空間計算量|時間計算量の時間を「メモリ」に置き換えて考え...
|平均計算量|全ての入力パターンに対し、それらの計算量を平...
|最大計算量|そのアルゴリズムにとって最悪のデータを使った...
#br
***オーダー [#o19a6d3b]
-ある関数g(n)と2つの定数c,n0が存在し、n>n0であるnについて...
f(n) < cg(n)~
が常に成り立つとき、f(n)=O(g(n))と記し、「計算量は''オー...
(十分大きなnに対しては、計算量f(n)はg(n)の定数倍である)
--例. f(n) = 2n~2 + n +5である場合のオーダー~
計算量は''O(n~2)''である。~
nが十分大きいとき、f(n) ≦ 3×n~2が常に成り立つ。
#br
**整列アルゴリズム一覧 [#c6d67f48]
|名称|処理内容|計算量|
|バブルソート|配列の先頭から後ろに向かってスキャンし、隣...
|選択ソート|未整列の(整列されていない)部分から最小の要素...
|挿入ソート|配列の一部を整列済みとし、残りの要素を一つず...
|ヒープソート|insert処理によって探索木を構築し、それに対...
|マージソート|データ列を真ん中で半分に分けていき、それぞ...
|シェルソート|hずつ離れた要素同士で整列を行っていき、hを...
|クイックソート|1つの要素を枢軸として定め、枢軸より小さい...
#br
終了行:
*プログラミング系 [#e3f5ea3d]
#contents
-[[back>ikeue2019/study]]
**問題&答え [#qce11870]
-編集中
#br
**計算量 [#g18a9681]
-プログラムにおいて、入力から出力を得るまでの「時間」につ...
-入力の数nに対し、出力が得られるまでの時間をnの関数で表し...
プログラムにおける計算量には、時間計算量以外にも様々なも...
|時間計算量|サイズnの入力に対して出力が得られるまでの時間...
|空間計算量|時間計算量の時間を「メモリ」に置き換えて考え...
|平均計算量|全ての入力パターンに対し、それらの計算量を平...
|最大計算量|そのアルゴリズムにとって最悪のデータを使った...
#br
***オーダー [#o19a6d3b]
-ある関数g(n)と2つの定数c,n0が存在し、n>n0であるnについて...
f(n) < cg(n)~
が常に成り立つとき、f(n)=O(g(n))と記し、「計算量は''オー...
(十分大きなnに対しては、計算量f(n)はg(n)の定数倍である)
--例. f(n) = 2n~2 + n +5である場合のオーダー~
計算量は''O(n~2)''である。~
nが十分大きいとき、f(n) ≦ 3×n~2が常に成り立つ。
#br
**整列アルゴリズム一覧 [#c6d67f48]
|名称|処理内容|計算量|
|バブルソート|配列の先頭から後ろに向かってスキャンし、隣...
|選択ソート|未整列の(整列されていない)部分から最小の要素...
|挿入ソート|配列の一部を整列済みとし、残りの要素を一つず...
|ヒープソート|insert処理によって探索木を構築し、それに対...
|マージソート|データ列を真ん中で半分に分けていき、それぞ...
|シェルソート|hずつ離れた要素同士で整列を行っていき、hを...
|クイックソート|1つの要素を枢軸として定め、枢軸より小さい...
#br
ページ名: