プログラミング系

問題&答え

  • 編集中
     

計算量

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

オーダー

  • ある関数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が常に成り立つ。
       

整列アルゴリズム一覧

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

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2020-08-11 (火) 12:44:51