『アルゴリズム4』読書ノート1.4-アルゴリズム分析(Analysis of Algorithm)

——————————————————————————— First priority is to make you code ** CLEAR and CORRECT, but PERFORMANCE** is also an essential, Keep Asking: How long will my program take, as a function of Input Size?
プログラムはまず簡潔で正確で、性能も無視できないでいつも自分に聞くことを覚えています:異なる入力の情況の下で、私のプログラムの性能はどうなりますか?—————————————————————————————————————
アルゴリズムの分析、退屈で抽象的で、私の粗浅な理解は複雑度(big-Oh)、運行時間、メモリの占有にとどまり、ばらばらである.『アルゴリズム4』の説明の構想はとても1セットのモードがあって、私も1時の科学研究を試みたような気がします.

基本的な考え方

冒頭の著者は2つの非常に関心のある2つの問題を提出した.
このプログラムはどのくらいで終わりますか?なぜ「メモリ不足」と間違えたのですか?
このようなアルゴリズム/プログラム分析に関する問題を解決するには、著者が提案した構想は抽象的で、脳を焼くが、システム、普遍的な知恵:
Base on the ** Scientific Method, Apply the Mathematical Analysis** to develop concise cost models Do the ** Experimental Studies** to validate these models
科学研究の方法に基づいて,数学解析を用いてアルゴリズムコストモデルを生成し,これらのモデルを種々の試験により検証した.
これはアルゴリズム分析の大きな方向であり,実際には多くの面で使用することができ,後で研究することができる.

科学的アプローチ（OHPVV）

科学的な方法は科学者たちが現実世界を理解するために使用しています.私たちがアルゴリズム分析を行うときもこの方法を適用することができます.私はOHPVVと略称します.
観察(Observe)仮定(Hyperthesize)予測(Predict)検証(Verify)確認(Validate)
科学者はこうします
現実世界の問題現象を観察して、はっきりと表現して、通常具体的な量子化を行って、例えばニュートンはリンゴが木の上から地面に落ちることを発見して、その時彼はすでに重力の吸引のためだと知っていて、彼は考えています:もしリンゴの木がもっと高くて、月のように高くても落ちるのではないでしょうか?どうして月が落ちなかったの?
前に観察された現象の可能性のある答えを推測し、仮定し、月が向心力の作用を受け、円周運動をしているので、落ちないと想定した.
その後,仮説や想定に基づいて予測を行い,自分の予測を検証し,最終的に万有引力の仮説を確認する.

科学的方法をアルゴリズム分析に応用する

アルゴリズム分析を行うとき、このような科学的な方法をどのように参考にしますか?

オブザーバは、所定の異なる入力の場合、どのくらい実行されますか?プログラムのキーコードセグメントの実行前後にタイミングコードを加えてdurationを計算することができます.

long start = System.currentTimeMillis()
.......
long end = System.currentTimeMillis()
long duration = (start - end ) /1000.0;

ここで無視しがちなのは,プログラムの入力(Input Size)が重要であることである.大きいファイルと小さいファイルの処理時間はきっと異なって、アルゴリズムの分析の1つの重点は、どのようにプログラムが大量に入力する情況の下で、依然として合理的な時間内に運行することができることを保証します.

数学モデルを構築し、シミュレーション計算プログラムの実行時間

Develop an input model, including a definition of the problem size

Identify the inner loop

Define a cost model that includes operations in the inner loop

Determine the frequency of execution of those operations of the given input.

簡単に言えば、プログラムの入力モデルを定義し、プログラムのコア消費時間コードブロック(通常、ループ文が比較的時間を占める)を探し出し、コアサイクルコードブロック内の操作コードのコストモデル(時間を費やす)を与え、異なる入力モデル(例えば最悪の場合)に対して、これらの操作コードの実行頻度を決定する.
二八原則を適用すると、ほとんどのプログラムの実行時間は、コアコードブロックの一部に依存するアルゴリズム実装である.
例分析:Binary Search

public static int rank(int key, int[] a){
        int lo=0;
        int hi = a.length -1;
        while (lo <=hi){
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid])       hi = mid - 1;
            else if (key > a[mid])  lo = mid + 1;
            else return mid;              
        }
        return -1;
    }

入力モデル:array a[N],size of Nコアループブロック:while loopコストモデル:配列値間の比較操作運転頻度分析:最悪lgN+1
3 . アルゴリズムを応用して試験・補正アルゴリズムを行う
これはアルゴリズム分析の基本的なやり方であり,把握している.具体的なコスト分析と頻度分析については、ここでは具体的に展開されず、後で単独で書きます.
では、アルゴリズムの分析をして、次はアルゴリズムを改善して、テストして、改善してからテストします.

まとめ

プログラマが新しい問題を解決する場合は、次のポリシーを推奨します.
Always keep asking "How long will it take, as a function of the input size?"
1.経典を参考にして、簡潔で正確な実装コード2.アルゴリズム分析、分析を行う:

入力(input model)

コアコードブロック(inner loop)

コストモデル(cost model)

運転頻度分析(analysis)

最悪の状況を分析することが重要だ.3.アルゴリズム4を改良します.新しいアルゴリズムをテストし、2,3,4を繰り返します.
アルゴリズムの分析はとても頭が熱くて、時間がかかります.一般的には専門の人がしなければなりませんが、普通のプログラマーは日常の仕事の中でいくつかのアルゴリズムの分析をマスターして、プログラムの性能を改善して、自分を早くもっと専門の人になることを向上させて、功績はありません.
もう一つ、数学は本当に重要で、とても重要で、とても重要で、当初数学をよく勉強しなかったことを後悔しています.学生時代、保護者の先生たちが口にした言葉は、「数理化をマスターして、天下を歩き回っても怖くない」と、今考えてみると、理にかなっている.