アルゴリズム入門

9045 ワード
python algorithm テキストリンク

アルゴリズム#アルゴリズム#


定義＃テイギ＃


限られたステップで問題を解決するステップまたは方法.主にコンピュータ用語に用いられ、コンピュータがある仕事を実行する段階的な方法を指す.

コンピュータ上でアルゴリズムを表現する方法


1.首都コード


2.シーケンス図


アルゴリズムの性能を測定する


APSカリキュラムの目標の一つは、より良いアルゴリズムを理解し、利用することです。


良いアルゴリズムとは何ですか?

  • 正しさ:
  • ワークロード:
    • はどのくらいの演算が必要ですか?
  • メモリ使用量:
    • メモリ使用量はいくらですか?
  • 単純性:どんなに簡単か
  • 最適:
    • は比類のない程度に最適化されていますか?
    与えられた問題を解決するために、さまざまなアルゴリズムを使用することができます.
    ->どのアルゴリズムを使うべきですか?
    アルゴリズムのパフォーマンスを分析する必要があります:多くの問題で、パフォーマンス分析を標準としてアルゴリズムのワークロードを比較します.
    #1.
s = 0 
for i in range(1,101) :
    s+=1
#2.
100*(100+1)/2

    アルゴリズムのワークロードを表現する際には,時間的複雑さで表す.


    時間の複雑さ

  • 実際の消費時間
    • 計算
  • 実行文数
    • #1 
def CalcSum(n) :
    sum =0
    for i in range(1,n+1) :
        sum=sum+i
    return sum

#2 
def CalcSum(n) :
    reutnr n*(n+1)/2

    ビオ記号法

  • big-ohマーキング法
  • 時間複雑度関数におけるnへの影響が最も大きい港湾は
    • を示した.
  • 係数を無視して
    • を表示
    #ex)
O(3n+2) > O(3n) > O(n)
O(2n^2 + 10n + 100) = O(n^2)
O(4) = O(1)

    整列

  • 資料構造
  • の例では、6つの変数を使用する必要がある場合は、アレイ
    • に変換する.
    Num0 = 0 ; Num1=1; Num2 = 2; Num3=3; Num4=4; Num5=5; == Num=[0,1,2,3,4,5]

    タイルが必要

  • プログラムでは、複数の変数が必要な場合、異なる変数名を1つずつ使用して資料にアクセスするのは非常に効率的ではありません.
  • 配列を使用すると、1つの宣言で2つ以上の変数を宣言できます.
  • は、複数の変数の宣言を意味するだけでなく、配列を用いて複数の変数では容易に完了しにくいタスクを完了することができる.

    • 1 Dアレイの宣言


    他の宣言メソッドがない場合は、変数の初期値を指定するときに
  • が作成されます.
    Arr = list()
Arr = []
Arr = [1,2,3]
Arr = [0]*10

    1 Dアレイの近似

  • Arr[0] = 10;//'「アレイArrの0番要素に10を格納」
  • Arr[idx] = 20;//'「アレイArrのidx番号要素に20を格納」

    • アレイ使用率の例:Gravity


    ツールバーの


    2つ以上のデータを特定の基準で小さい順から大きい順に並べ替える


    身長

  • データの特定ソート値
  • ex)ファイル番号、カード番号

    • ソートのタイプ

  • バブルソート(重要)
  • 隣接する2つの要素を比較し、交換位置
    • を継続する.
  • ソート・プロシージャ
  • は、第1の要素から始まり、最後の位置まで隣接する要素間で位置を交換し続ける.
  • の1段階が終了すると、最大の要素は最後の位置
    • に並ぶ.
  • 交換後、移動位置の様子は水面上の泡と同じで、泡配列と呼ばれます.
  • 時間複雑度:O(n^2)
  • カウントソート
    効率的な線形時間ソートアルゴリズム
    • は、セット内の各項目の数を計算し、それらの順序を決定する.
  • 制限
  • で整数または整数として表すことができる資料にのみ適用されます.各項目の発生回数を記録するために、整数項目をインデックスとするカウントシーケンスが使用されるためです.
  • のカウントダウンに十分なスペースを割り当てるには、セット内の最大の整数を知る必要があります.
  • 時間複雑度:O(n+k):nはリスト長、kは整数最大
  • 選択ソート
  • クイックソート
  • 挿入ソート
  • 連結ソート

    • シーケンス(フルナビゲーション)


  • ひとつながり

  • 異なるnにおいて、r個を選択する手順を以下に示す.

  • nprは次のように構成される.
    nPr = n*(n-1)*(n-2)*...*(n-r+1)
#n에서 1만큼 빼가며 r번 곱한다.

    • グレースケールアルゴリズム

  • 貪欲アルゴリズム最適解を解くための短視法
  • 多くの場合、その中の1つを決めるたびに、その瞬間に自分が一番適当だと思っているものを選んで、外に出る方法で行い、最終的な答えに達します.
  • の選択の観点からの決定は地域的に最良であるが、これらの選択を収集し続け、最終的に答えを出した場合、それが最良であることは保証されない.
  • 一般的には、検証を必要とせずに頭の中の考えを実現するGreedyメソッドです.

    • GRADYアルゴリズム操作手順


  • ≪年選択|Year Selection|emdw≫:現在の状態でローカル問題の最適解を求め、その部分をコレクションに追加します.

  • 実行可能性チェック:新しい部分解セットが実行可能かどうかを確認します.すなわち、問題の制約条件に違反しているかどうかを確認します.

  • 解チェック:新しい部分解集合が問題の解になるかどうかを確認する.問題全体の年がまだ完成していない場合は,1)の年選択から再開する.

    つりを減らす



  • お客様におつりを出す紙幣とコインの個数を最小限に抑えるにはどうすればいいですか?
    1)年選択:ここは遠くを眺める必要がなく、最高の年を選ぶ.大きなコインだけで小銭を探すと、コインの個数が減るので、今選べる最大単位のコインを選んで、おつりに追加します.
    2)実行可能性検査:おつりがお客様に渡すべき金額を超えているかどうかを確認します.超える場合は、最後に追加した硬貨をおつりから外して1)に戻し、今より一歩小さい単位硬貨を追加します.
    3)海検事:お金を探す問題の年は、もちろんお金を探すのはお客さんにあげる金額と一致します.いくらあげても少なめにはあげられないので、おつりが足りないことを確認したら、また1)に戻り、おつりにつけるコインを選びます.
    • 複数のdivは、改行せずに同じ行に並べられます.
    ブールモルアルゴリズム