[アルゴリズム解析]効率

1.アルゴリズム
問題を解決できる定義が良好な有限時間内に終了する計算プログラム.
入力を受信して出力に変換する一連の計算ステップ.
アルゴリズムはプログラムエンジンの重要なステップです
2.疑似コード
直接実行可能なプログラミング言語ではないが,計算プロセスは実際のプログラムに近い言語でほとんど表現できる.
3.フローチャート
4.シーケンシャルサーチアルゴリズム
質問:nサイズのアレイSにxはありますか?
入力:n,S[n],x
出力:xがある場合は位置、-1がない場合は
鍵を検索するには、S上の何個のアイテムを検索する必要がありますか?
->プロジェクトの場所によって、n回
もっと早く見つけられますか?
->他の情報がない限り不可能です
5.二分探索アルゴリズム
質問:サイズnの配列Sにxはありますか?
入力:n,S[n],x
出力:xがある場合は位置、-1がない場合は

int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return -1;
    }

二分探索アルゴリズムで鍵を検索するには、S上のいくつかの項目を検索する必要がありますか?
->while文を実行すると、検索オブジェクトのサイズが半減し、logn+1個を検索するだけです.
6.数学的帰納法
(1)帰納起点n=0(または1)において主張が事実であることを示す
(2)仮説をまとめる:あるnの主張が事実であると仮定する
(3)帰納手順:n+1の陳述が事実である
7.アルゴリズムの分析

空間複雑度(空間複雑度)

プロセスでは、入力サイズに基づいてワークスペース(メモリ)を決定します.

時間複雑度(時間複雑度)
ステップ

では、入力されたサイズに応じて単位演算を何回実行するかを決定する.
8.分析方法の種類

すべての状況分析(ever-case分析)
入力サイズのみに関係し、値に関係なく
結果値は、入力値に関係なく常に固定されます.

さいあくじょうたいぶんせき
入力サイズと入力値に依存
単位演算を実行する最大回数を選択

平均ケーススタディ
入力サイズに依存
全ての入力に対して単位演算を行う期待値(平均値)
入力ごとに確率を割り当てることができます
計算は通常最悪の場合より複雑です

ベストケーススタディ
入力サイズと入力値に依存
単位演算を実行する最小回数の選択

9.精度分析
正しいアルゴリズム=任意の入力に対する答えの出力を停止するアルゴリズム
不正なアルゴリズム=ある入力に対して停止しない、または誤った答えを出力したときに停止するアルゴリズム