時間の複雑さ

4374 ワード
dynamic programming Big O シミュレーション フルナビゲーション 時間の複雑さ greedy algorithm テキストリンク
効率的なアルゴリズムを実現します.
すなわち,入力値が大きくなるにつれて増加する時間の割合を最小化するアルゴリズムを構築した.

1.時間の複雑さ


  • 入力値の変化に応じて演算を実行するのに要する時間(演算回数に対して)を表します.
    時間の複雑さをマークする方法
  • Big-O:上象限漸近(最悪)
    • 大-ω:下限漸近(最適)
  • Big-θ (大-3打):平均(中)

  • その中で最もよく使われるのがBig-Oマーキング法です.bigoタグ法は最悪の場合を考慮しているので,プログラムの実行に要する最悪の時間を考慮することができる.

  • bigoは、入力値の変化に応じて演算を実行する場合、演算回数に対してどれだけ時間がかかるかを示す方法である.

    • 1. O(1)

  • O(1)を定数複雑度と呼び,入力値が増加しても時間は増加しない.すなわち,入力値の大きさにかかわらず,直ちに出力値を得ることができる.
    例)arrayのインデックス値を検索する

    • 2. O(n)

  • O(n)を線形複雑度と呼び,入力値の増加とともに時間も同様の割合で増加した.
    • 例えば、入力値が1の場合は1秒、入力値が100倍の場合は1秒の100倍という100秒のアルゴリズムが実現されると、このアルゴリズムはO(n)の時間的複雑さを有する.
    例)1つのfor文で配列をナビゲートする

    3. O(log n)

  • O(logn)を対数複雑度と呼び,Big‐Oマーキング法ではO(1)に次いで高速時間複雑度を持つ.
  • nが与えられた場合、1/2減少し続けるため、演算回数がlog 2(n)であればbig−oで表され、lognである.
    例)バイナリ検索ツリー

    • 4. O(n^2)

  • O(n^2)は二次複雑性と呼ばれ,入力値が増加するにつれて時間がnの平方数の比率で増加することを意味する.
    • 例えば
  • では、入力値が1の場合、1秒のアルゴリズムに5の値が与えられ、25秒が必要な場合、アルゴリズムの時間複雑度はO(n^2)と表される.
  • n^3とn^5もO(n^2)と表記されている.nが大きいほど、指数が与える栄養力は色あせるので、このようにマークされる.
    例)ドアには2つのオーバーラップがあり、ドア
    • には3つのオーバーラップがある

    5. O(2^n)

  • O(2^n)を指数複雑性と呼び,Big−Oマーキング法では最も遅い時間複雑度を持つ.
    例)再回帰フィボナッチ数列

    • 時間の複雑さはデータのおおよその大きさによって決まる



    例題

  • Q.アルゴリズムが以下の時間複雑度を有する場合、最も遅く、最も速いのは?
  • O(n)
  • O(2^n)
  • O(log n)
  • O(n^2)
  • O(n!)
  • A.最も速い-O(logn)/最も遅い-O(n!)

    • 2.貪欲アルゴリズム

  • を選択した瞬間に、目の前の最良の状況だけを求めて、最終的な答えを得る方法
  • 貪欲アルゴリズムの問題を解決する過程で、一瞬ごとに自分が最適だと思っている答え(局所最適解)を見つけ、それに基づいて最終問題の答え(グローバル最適解)を達成する問題解決方法.しかし、このソリューションは常に最適な結果を保証するものではありません.特定の状況でしか答えがないからだ.
  • 貪欲アルゴリズムは必ずしも最適な結果を得ることができないが,その利点はある程度最適近似値を迅速に得ることができることである.
  • 貪欲アルゴリズムを適用するには、解決すべき問題は以下の2つの条件を備えなければならない.
    1.貪欲な選択プロパティ:前の選択は後の選択に影響しません.
    2.最適局所構造:問題の最終解決方法は局所問題の最適解決方法からなる.

    • 3.動的計画（DP；動的計画法）

  • 貪欲アルゴリズムのように、小さな問題から出発します.しかし,貪欲アルゴリズムが一瞬ごとに最適な選択を探す方式であれば,DPはすべての場合の数字を組み合わせて最適な解法を探す方式である.
  • DPの原理は、与えられた問題を複数のサブ問題に分解し、サブ問題の解決方法と組み合わせて最終的な問題の解決方法を解決することである.サブ問題を計算して解決策を保存し、後で同じサブ問題に遭遇した場合に保存した解決策を適用し、計算回数を減らす.すなわち,一つの問題を一度だけ解くアルゴリズムがDPである.
  • は、以下の2つの家庭が満たす条件で使用することができる.
    1.大きな問題を小さな問題に分けて、この小さな問題を繰り返し発見することができます.(重複問題)すなわち大きな問題から分離された小さな問題は,大きな問題を解決する際に複数回繰り返し使用できるはずである.
    2.小さな質問で求めた答えは、それを含む大きな質問でも同じです.すなわち,小問題で求めた答えは大問題でも用いることができる.(Optimal Substructure)とは,与えられた問題の最適解法を解くには,与えられた問題の小さな問題の最適解法を見つけなければならないということである.次いで,小問題の最適解法と組み合わせて,最終的に問題全体の最適解法を求めることができる.
  • DPは、サブ問題の解決策を保存し、同じサブ問題が発生した場合は、保存された解決策を使用する.このとき結果を保存する方法を記憶といいます.
  • メモリの定義は、コンピュータプログラムが同じ計算を繰り返す必要がある場合に、以前に計算した値をメモリに格納し、同じ計算の繰り返し実行を排除し、プログラムの実行速度を速める技術である.

    • 4.完全探索

  • 完全探索とは、可能な限り全ての数を確認して問題を解決する方法である.
  • すべての問題は完全に探索によって解決することができる.この方法は非常に簡単で無知だが、「答えは無条件」の強さがある.
  • 完全ナビゲーションとは、単純にすべての状況でナビゲーションされるすべての状況を指す.完全ナビゲーションの方法には、brute force(使用条件/繰返し解決)、再帰、シーケンス、DFS/BFSなどがあります.

    • 5.シミュレーション

  • シミュレーションは、シミュレーションのように、問題で要求される複雑な実装要件をコードに漏らさずに移行する.
  • シミュレーションは、プロセスの結果がどのようなタイプであるかを確認するすべてのプロセスおよび条件を提供する.通常,問題で説明した論理に従ってコードを記述すると,問題の解決策が容易に考えられるが,詳細なコードに変換することは困難である.

    • 6.クロム開発者ツールで関数実行時間を測定する方法

    var t0=performance.now();
실행할 함수 쓰기
var t1 = performance.now();
console.log(“runtime: “ + (t1-t0) + ‘ms’)
    組み込み型オペレーティングシステム開発プロジェクトCH 6
    96.時刻