【アルゴリズム】アルゴリズム図解ノート_アルゴリズムの概要

2513 ワード

ハスカル python アルゴリズム

『アルゴリズム図解』という本を読むと、この本には2つの利点があります.

手描きスタイルの図は、「芝居に入る」ように見えます.

アルゴリズムはPython言語記述を採用し、アルゴリズム思想をよりよく表現することができる.

アルゴリズムの学習には2つの心得があります.

アルゴリズムの思想は最も重要で、思想を理解して、アルゴリズムはとても書きやすいので、できるだけ多くの精力を細部に置かないでください.例えば,本書の迅速なソートは,リスト導出式を用いてアルゴリズムの考え方を簡単に記述した.それに比べて、C言語を使った本のバージョンが分かりにくいのは、細部が際立っているからです.詳細は重要ではありませんが、まずアルゴリズムをよりよく理解しなければなりません.次のステップは実現と最適化です.

は、反復よりも再帰的に表現しやすい場合があり、アルゴリズムの性質の表現に重点を置いている.反復はアルゴリズム実装に重点を置き,実装の詳細が多すぎることが多い.したがって,私は同時にHaskellを用いて再帰バージョンのアルゴリズム記述を与えた.

さあ、始めましょう.
引用する
アルゴリズムは、タスクを完了する命令のセットです.どのコードフラグメントもアルゴリズムと見なすことができます.[注意:この本のアルゴリズムの定義は通行の定義とは異なり、通行の定義はアルゴリズムに貧乏性を持たなければならない.すなわち、アルゴリズムは限られたステップを実行した後に終了しなければならない.そうしないと、アルゴリズムは意味がない.]
本書では、統合ソートアルゴリズムを使用するか、高速ソートアルゴリズムを使用するか、配列を使用するかチェーンテーブルを使用するか、異なるアルゴリズムの長所と短所を比較することを学びます.異なるデータ構造を変更するだけで結果が大きく異なる可能性があります.
二分検索(binary search)
その入力は秩序化された要素のリストです.検索された要素はリストに含まれ、二分検索はその位置を返します.そうでなければNothingに戻ります.一般に、n個の要素を含むリストについては、最大log 2 nステップを二分で検索する必要がある.
Pythonバージョン:

def binary_search(list, item):
    low = 0
    high = len(list)—1
    
    while low <= high:
        mid = low + (high-low) / 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

Haskellバージョン:Vectorが使用されています.標準ライブラリのリストは単一チェーンテーブルであり、ランダムアクセスはサポートされていません.

import qualified Data.Vector as V

binarySearch :: (Ord a)=>  V.Vector a -> Int -> Int -> a -> Maybe Int
binarySearch vec low high e
          | low > high = Nothing
          | vec V.! mid < e = binarySearch vec (mid+1) high e
          | vec V.! mid > e = binarySearch vec low (mid-1) e
          | otherwise = Just mid
          where
              mid = low + (high-low) `div` 2

大O表現
アルゴリズムが実行されるまでどのくらいかかるかを知るだけでは十分ではありません.また、リストの増加に伴って実行時間がどのように増加するかを知る必要があります.
アルゴリズムの実行時間は異なる速度で増加する
アルゴリズムの速度は時間ではなく,操作数の増加率を指す.アルゴリズムの速度について述べると,入力が増加するにつれて,その実行時間がどのような速度で増加するかを述べる.大きなO表現は操作数を比較することができ、アルゴリズムの実行時間の増加率を指摘しています.
大O表示法は最悪の場合の運転時間を指摘している
これは、単純な検索の実行時間がO(n)を超えないことを保証します.
いくつかの一般的な大きなO運転時間
O(log n)は、対数時間とも呼ばれ、このようなアルゴリズムは二分検索を含む.O(n)は、線形時間とも呼ばれ、このようなアルゴリズムは簡単な検索を含む.O(n*log n)は、高速ソートを含む、より高速なソートアルゴリズムである.O(n 2)は、速度の遅いソートアルゴリズムの選択ソートを含む. O(n!),このようなアルゴリズムには旅行者の問題の解決策が含まれています.非常に遅いアルゴリズムです.
旅行者問題
旅行者はn都市に行くと同時に、旅が最も短く、時間の複雑さ:O(n!)を確保しなければならない.
私の公衆番号に注目してくださいね.

JBoss AS 6.1.0 Final起動パラメータの役割とサービスの選択

異なるバージョンのjbossのメッセージ構成