ログイン
サインイン

マインドマップギャラリーアルゴリズムの分析と設計

アルゴリズムの分析と設計

アルゴリズムの分析と設計に関するマインドマップアルゴリズムとは、終了、確実性、実現可能性、入力と出力の条件を満たす計算です。最適解を見つけるためにどのアルゴリズムが使用されるとしても、最適解が何であるかを明確にする必要があります。

2023-10-28 17:00:08 に編集されました

WSUJfrxa

最近の作品その他の作品を表示>>

アルゴリズムの分析と設計

WSUJfrxa

最近の作品その他の作品を表示>>

おすすめ
アウトライン

古典的な数値アルゴリズムとその Maple 実装
- 8
WSUJfrxa
アルゴリズムのブラックボックスによる課題と情報クラッキング — アルゴリズムを解釈する権利に焦点を当てる
- 9
WSUJfrxa
1. 歯の解剖学と生理学 - 切歯、犬歯、小臼歯
- 5
WSUJfrxa
Douyin公式推奨アルゴリズムコミュニケーションコンテンツ集
- 11
WSUJfrxa
アルゴリズムの基本的な制御結果とその応用を理解する
- 6
WSUJfrxa
アルゴリズムの概要
- 14
WSUJfrxa
データ構造 - アルゴリズムマインドマップ
- 12
WSUJfrxa
人工知能のトップ 10 アルゴリズム
- 11
WSUJfrxa
[408]データ構造とアルゴリズム
- 5
WSUJfrxa
アルゴリズムを効率的に学ぶ方法
- 19
WSUJfrxa

アルゴリズムの分析と設計

第1章;序章

アルゴリズムとは、以下の条件を満たす計算のことです。

目的: 問題を解決する

終了可能性

確実

実現可能性

入力

出力

計算する

给定计算模型机械的执行的规则或计算步骤序列被称为计算

一个计算机程序是一个计算

計算はアルゴリズムではありません

質問

入力と出力の関係を定義します

アルゴリズム秋祭りは単純な問題インスタンスではなく、完全な問題です

解析アルゴリズム

アルゴリズムの正確性: すべての入力に対して終了し、正しい出力を生成します。

不正なアルゴリズム: 入力に対して終了しないか、誤った出力が生成されます。

近似/確率的アルゴリズムの正確さ: すべての入力に対して終了し、ほぼ正しい解または少数の誤った解を生成します。

正当性証明の理由

プログラムをデバッグしても、エラーがないことを証明することはできません

方法

すべての入力で終了する

すべての入力には正しい出力が含まれます

アルゴリズムの複雑さ

目的: さまざまな入力に対してアルゴリズムが必要とするリソースの量を分析します。

時間計算量、空間計算量、入出力の数など。

入力サイズ関数

入力サイズ：サイズ(α)

インスタンス時間の複雑さ: 特定の入力の結果を生成するために最も必要な操作の数

特定の入力の時間計算量

インスタンススペースの複雑さ

特定の入力

空间复杂性，对输入产生结果所需要的存储空间大小

是输入大小的函数S(n)

最悪の時間複雑さ

アルゴリズムの最小複雑さ

平均的なアルゴリズムの複雑さ

発生確率に複雑さのすべての可能性の合計を乗算したもの

アルゴリズム分析モデル

ランダムアクセスモデル

並列マルチプロセッサモデル

時間計算量の分析

プログラムが問題を解決するのに時間がかかるのではなく、問題の規模が拡大すると、その時間の長さが非常に早く長くなるのです。

一定レベルの時間計算量

直接挿入アルゴリズムの時間計算量解析

k 番目の数値を読み取るときに、前の数値と積極的に比較し、

アルゴリズムの正確性分析

ループ不変メソッド

ループ不変式 P: データと操作対象のデータ構造には重要なプロパティがあります

たとえば、並べ替えアルゴリズムでは、数値の順序が変わらないという特性をループの不変条件として使用できます。

ループの初期化

サイクルステップ

ループが終了しました

設計アルゴリズム

分割統治

動的プログラミング

貪欲なアルゴリズム

ツリー検索アルゴリズム

問題分割

チューリングマシン

決定論的チューリングマシンは問題 P を多項式時間で解きます

多項式時間の不確実なチューリングマシンによって解ける問題 NP

不確実なチューリングマシンは非 NP にできなくなりました

サブトピック

第 2 章数学の基礎

2.1 複雑さ関数の次数の計算

同じ次数の関数のセット f(x)=θ(g(x)) ここで、関数のセットは次のとおりです: θ(g(x)) タイトバウンド

低次関数 f(n)=0(g(n)) の上限は、それよりも低い次の上限である可能性があります。

高次関数 f(n)=Ω(g(n)) 下限のベストケース

それはサイズの関係を説明することはできず、クラスの関係を説明することしかできません。高階関数は必ずしもその下限よりも大きいとは限りません (厳密には高階関数ではありません)。

θ(g(n))⊆0(g(n)) f(n)=O(n^k ) 多項式の範囲

厳密に低次関数の上限はあるが、厳密な境界ではない f(n)=o(g(n))

f(n)=o(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =0

厳密に高階関数の下限はあるが、厳密な境界ではない f(n)=ω(g(n))

g(n)=o(f(n)) の場合に限り、f(n)=ω(g(n))

f(n)=ω(g(n))⇒(lim)┬(n→∞) f(n)/g(n) =∞

関数の次数の性質

推移性には上記の5つが含まれます

反射性には最初の 3 つが含まれます

対称性のタイトバウンド

反対称

g(n)=Ω(f(n)) の場合に限り、f(n)=0(g(n))

g(n)=ω(f(n)) の場合に限り、f(n)=o(g(n))

数式における関数の順序の意味

2.2 合計の推定と限界

線形和

シリーズ

直接加算の範囲

サブトピック

2.3 再帰方程式はそれ自体を定義するためにそれ自体を使用します

再帰方程式を解くための 3 つの主な方法

代入推測の数学的帰納法

反復して合計に変換し、合計を推定します

マスター定理

サブトピック

第3章選別と分割統治のアルゴリズム

3.1 分割統治の原則

設計段階

ポイント: 部分問題の分割時間 D(n) は同じではない可能性があります。

ガバナンス: 各サブ問題 aT(n) を解決します。

合計: 部分問題 C(n) に対する解を結合します。

合計時間計算量: T(n) = a(T(n/b)) D(n) C(n)

分析段階

再帰方程式を構築する

解決する

3.2 分割統治に基づく並べ替えアルゴリズム

クイックソートの主な仕事は分割アルゴリズムを実行することであり、境界条件を知る必要があります。

並べ替え問題の下限

3.3 中央値と次数の統計

削減の原理

たとえば、半分で検索します。

質問を選択してください

3.4 最も近い点のペアを見つける

f(n) を減らすための分割と結合の方法

1次元空間アルゴリズム

最初に並べ替える

分割統治アルゴリズム

ポイント

ルール

そして

2次元空間アルゴリズム

3.5 線形時間でのソート

数える

3 つの配列 A、B、C を使用します

全体的な考え方: 入力配列 A、出力配列: B、カウント配列: C [配列のベースは A の値の範囲 [0-k [A の最大値]]] (要件: A は整数配列である必要があります)

【注意】消費スペースが大きい場合はバケット構造をご使用ください。

問題点

A[i] は整数です

また、入力配列 0 ～ k の値の範囲を小さくする必要があります。そうしないと、効率が大幅に低下します。

ソート処理中に、最大長の計数スペースと長さ len の補助出力スペースが必要になります。このスペースは比較的大きく、スペースの複雑さは O(len max) です。

時間計算量: O(n k)

基数

特徴

安定した

最低から最高の順に並べ替えます

アルゴリズム

入力要件: 同じ桁数の配列整数 d

時間計算量: O(d(n k[入力値の範囲、影響は比較的小さいため無視できます]))

問題: d が大きすぎます

分割統治アルゴリズムを使用して拡張

b 桁の配列を b/r に分割し、r 桁から上のデータ全体を取得します。各データの値の範囲は 0-2^r-1 です。

カウントを使用して並べ替える

rの最適値：lgn切り捨て

注: r が大きくない場合に使用できます。

バケットバケットソート

バケットソートの仮定: 入力は 0 ～ 1 の間で独立して均一に分散されます [線形性が達成されると予想される条件]

バケツの仕分けアイデア

0 ～ 1 を均等なサイズのバケットに分割します

入力はバケットに分類されます

バケット内のデータの並べ替え

各バケット内のソートされたすべてのデータをリストする

時間計算量: タイトな限界 n

アルゴリズムを判断するためのいくつかの基準

stable：按照输入顺序合理的排序输出

in-place：没有另外开辟空间

3.6 凸包を求める

問題定義

入力: 平面上の点の集合、出力の凸包

自然

凸多角形 P の場合、P 内の任意の 2 点を結ぶ辺はすべて P 内にあります。

グラハムスキャンアルゴリズム

反時計回り、極角サイズでソート

左に回転

知らせ

xy の最大値と最小値はすべて凸包上にあります。まず、いずれかの点を開始点として決定し、水平線を引き、この水平線を起点として上記の点をトラバースします (最小の点が選択されます)。

疑似コード

Q 内の最小の y 座標値を持つ点を見つけます

Q の残りの点を反時計回りに並べ替えます

スタック S にプッシュ

構成料が左に移動した場合は、スタックの一番上の要素をポップアウトします。

時間計算量: f(n)=0(n log⁡n)

正当性解析：ループ不変 [あるノードを処理する前にスタックSにCH(Qi-1)を下から上に格納する]

分割統治アルゴリズム

境界条件

ポイント

Ql、Qrに分割

ルール

そして

マージされたシーケンスに対して Graham-Scan を実行するだけです

シーケンスをマージする方法

3.7 高速フーリエ変換 FFT

3.8 整数の乗算

分割ステージを最適化して、

問題の定義: 入力 - n ビット 2 進整数 X および Y 出力 - X と Y の積。

第 4 章動的計画アルゴリズム

アルゴリズムの概要

疲労感がある

就是罩子问题和服问题之间的关系之后再使用穷举的方法最后选定最小值作为最优解

注意：覆盖所有情况

4.1 動的プログラミングの要素

理由: サブ問題が互いに独立していない場合、スコア法では共通のサブ問題が繰り返し計算されるため、非常に非効率的です。

目的: 最適化問題 - 最適化問題は、コスト関数を与えることです。問題の解決空間を検索して、最小または最大のコストで最適な解決策を見つけます。

動的計画問題は、最適化問題を解決するための一般的なアプローチです

定義: 元の問題は一連の部分問題 [多項式レベルの数] に分割されます。

部分問題をボトムアップで解決する

トップダウンの分割統治アルゴリズム

適用範囲：再利用可能な部分問題として解決できるタイプの問題

利用条件

部分構造の最適化: 問題の最適解に部分問題の最適解が含まれている場合、これを「部分構造の最適化」といいます。問題には最適化の下部構造があります。

重複する部分問題: 問題の解決プロセス中に、多くの部分問題の解決策が複数回使用されます。

重複がない場合は、分割統治を使用します。重複しない場合は、追加のストレージスペースを作成する必要があります。

アルゴリズム設計の手順

– 最適解の構造を分析します（どの部分問題が最適解で構成されているか、境界条件に進むだけです） – 最適なソリューションのコストを再帰的に定義します – 部分問題を分割できなくなるまで再帰的に分割します – 各サブ問題をボトムアップで解決します – 最適化ソリューションのコストを計算して保存します – 最適なソリューションを構築するための情報を取得する – 最適解を構築するために使用された情報に基づいて最適解を構築する

4.2 行列連鎖乗算

問題の定義: 入力 p_i-1*p 行列、最小コストを計算する方法を出力します。

行列乗算

結合法則を満たします。異なる計算順序には異なるコストがかかります。

動的プログラミング手法を使用する

重複する副次的な問題がある

最適解のコストを再帰的に定義する

サブトピック

拡張ソリューション: 暗記法を使用でき、スコアを動的プログラミングに変換できます。

4.3 最長共通部分列

問題定義

問題解決

⚫ 最適解の構造解析 ⚫ 最適解を求めるコスト漸化式を確立する ⚫ 部分問題を再帰的に分割する ⚫ 最適化ソリューションのコストをボトムアップで計算し、最適化ソリューションの構築情報を記録します ⚫最適化ソリューションの構築

最適化された下部構造解析

i 番目の接頭辞: Xi

下部構造の最適化

このメソッドを再帰的解決に使用すると便利です

3つの直接的な証拠

サブ問題の重複、処理する必要がある問題の数 (最大で mn 個のサブ問題)

あらゆる状況をカバーするのが最善です

境界条件の計算を容易にするため

境界条件の計算が不便な場合、境界の計算には最大でも O(m) または O(n) 時間がかかります。

問題の分割: 上で定義した条件、つまり、再帰のために以前に定義した条件を使用します。

最適化ソリューションのコストをボトムアップで計算し、上記のソリューションに基づいて下方に解決します。

最後に、下から上に解き、B でマークされた最適解の記号に従って解きます。得られる解は、最終解の反転です。

疑似コード: 解決策は行ごとに検索され、矢印を使用して下から上の検索が行われます。

時間計算量: O(mn) [部分問題の数]、最適解を構築するのにかかる時間は O(mn)

空間の複雑さ O(mn)

スペース最適化戦略: C を 2 行 m 列のみに設計することもできます。

4.4 0/1 バックパックの問題

問題定義

重量を超えずにバッグ内のアイテムの価値を最大化する梱包戦略を開発する

予備分析: 各アイテムに設置するか設置しないかの 2 つのオプションがあります。設置および撤去計画の計算コストは n です (ティーカップ/値を計算する場合は、最大値を取得するために定数時間を使用して比較します)。

総計算コストは O(n2^n) です

np 完全な問題

問題解決

最適解の構造解析

部分問題の重複: アイテムの重みが同じで両方とも 1 の場合、重複する部分問題が多数存在します。

分割統治アルゴリズムには適していません [メモ化を使用してみることができます]

問題定義

解決コストを最適化する再帰方程式を確立する

コスト行列 m を定義します。

m[i,j]

i:起始的、计算子问题优化解的代价的矩阵时间

j:指的是包的容量

再帰方程式のまとめ

再帰的分割サブ問題

m[i,j] を計算するために知っておくべきこと

最適化ソリューションのコストをボトムアップで計算し、最適化ソリューションの構築情報を記録します

最適化ソリューションの構築

総コスト計算: 擬似多項式アルゴリズム

シチュエーションは全部で4つあります

4.5 二分探索木

問題定義

二分探索木の定義

検索ツリーの全体的なクエリコストに影響します。ツリーの形状とノードのクエリ確率です。

ツリーの期待値

奇数番号のノードはリーフノードです

偶数番号のノードは内部ノードです

E(T)ツリーのコスト期待値

コスト値はツリーの深さとコストの増分に関連します。

ルートノードは偶数である必要があります

問題解決

最適解の構造解析

最適化された基礎構造と証明

サブツリーの寄与値: サブツリーの位置、確率は固定されており、寄与の差は一ツ星です。

貢献度の増加: 確率 * 深さの差

最適化部分構造を使用して最適なソリューションを構築する

サブ問題の重複

解決コストを最適化する再帰方程式を確立する

最適解を求める検索コストの再帰方程式を確立する

境界条件とその他の考慮事項

すべてカバーされています

計算式: 確率 (コスト増分) [左のサブツリー、右のサブツリー]

W: 増分、E: 予想コスト、P: 確率。

インクリメンタル再帰計算式

W[i,j] = w(i,j-1) pi pj = w(i,r-1) w(r 1,j) pr

再帰的分割サブ問題

最適化ソリューションのコストをボトムアップで計算し、最適化ソリューションの構築情報を記録します

最適化ソリューションの構築

4.6 最小編集距離

意味

2 つの文字列間の変換

含まれる操作は 3 つだけです: 文字の挿入、文字の削除、文字の置換 [それぞれが基本操作としてカウントされます]

文字の配置は効率に影響します

解決する

最適解の構造解析

最小編集距離のプロパティ

非重複: どのキャラクターも最大 1 つの操作のみを実行できます。

順序の独立性

対称

空の拡張文字列

サブ問題の重複

解決コストを最適化する再帰方程式を確立する

4つの状況

境界条件

まず、計算を開始するための条件として境界条件を考慮する必要があります。

アルゴリズムとアルゴリズムの複雑さ

時間計算量 O(mn)

空間の複雑さ: O(mn)

空間構造の最適化

再帰的分割サブ問題

最適化ソリューションのコストをボトムアップで計算し、最適化ソリューションの構築情報を記録します

最適化ソリューションの構築

最小編集距離判別問題

応用

字符串的相似度查询

意味

入出力

分析する

最小編集距離は、2 つの長さの絶対値以上です。

複雑

計算が必要ない 2 つの状況

長さの差が入力判定しきい値を超えています

計算では、2 より大きい上記の結果値を使用する必要があります。

空間の複雑さ

O(min{m,n}t): 最適化可能

O(t)

時間の複雑さ

O(min{m,n}t)

各行/列は最大 2*t 1 を計算できます

第5章貪欲なアルゴリズム

前の 2 つのアルゴリズムとの違い

子主题

贪心算法：原问题进行选择获取剩余子问题直至子问题为空

繊細

前面两种：原问题划分为子问题，繁重，自底向上

5.1 基本原則

基本的な考え方

近似アルゴリズム、ヒューリスティックアルゴリズム

局所最適解、現時点での最良の選択

例

両替コイン問題

地域のスケジュールの問題

使用

最適化問題を解く

基本的な考え方

最適化問題を解決するためのアルゴリズムは一連のステップで構成されており、各ステップには現時点で最善の選択を行うための一連の選択肢が含まれています。

世界最適解の実現を目指します

段階的に試してから、オーバーロードしたり、他のことを試して貪欲なアルゴリズムを見つけてください

徐々に最適解に近づき、最終的には最適解に到達する

例

最適解が生成される条件

下部構造の最適化

貪欲な選択的

誘導

アルゴリズムのステップを要約するか、問題を要約します。

各ステップは他のアルゴリズムよりも優れており、最適なソリューションを生成します。

含まれる各ステップのソリューションは、含まれるステップにとって適切なソリューションである必要はありません

可換引数

もっと便利

最適性が変わらないという前提の下で、最適解から徐々に置き換えていき、最終的に貪欲アルゴリズムの解を取得します。

比較する

設計ステップ

貪欲な選択アルゴリズム

残りの副問題

証拠が必要です

对于贪心选择来说，所求解的问题具有优化子结构

对于贪心选择算法莱说，具有Greedy选择性

5.2 アクティビティ選択の問題

問題定義

問題解決

貪欲な選択方法の設計

最適解の構造解析

貪欲な選択的証明

補題 1

貪欲な選択性の実証

【注意】最適解の条件は何かを明確にする必要があるこの問題では、最適な解決策は最も一貫したアクティビティです。数量と互換性の特性によって異なります

補題 2: 部分構造の最適化

矛盾による証明

補題 3

アルゴリズム設計

アルゴリズムの複雑さの分析

5.3 ハフマン符号化

問題定義

バイナリ文字エンコーディング

固定長エンコーディング

可変長エンコーディング

プレフィックスエンコーディング

意味

コーディングツリー

コーディングツリーのコスト: コストは、予想される深さの合計です。

C: 文字セット

B: コストの合計

F: 周波数

貪欲な考え

ツリーが形成されるまで、頻度が最も低い 2 つのノードを周期的に選択してサブツリーを生成します

問題解決

貪欲な選択方法の設計

選び方

残りの部分問題の構造

最適解の構造解析

補助定理 1: 最適化された部分構造の証明

補助定理 2: 最も深い位置、最小任命レターの 2 文字、同じ最大長

貪欲な選択性

同じ深さの 2 つのノードの最大長を含むようにプレフィックスツリーを最適化します。

貪欲な選択的証明

アルゴリズム設計

アルゴリズムの複雑さの分析

5.4 最小スパニングツリー

問題定義

クラスカルアルゴリズム

デザイン

ソリューション構造の最適化

残りの副問題

縮小操作

拡張操作

最適化された基礎構造証明

貪欲な選択的

アルゴリズムの複雑さ

アルゴリズムの正確さ

プリムのアルゴリズム

デザイン

ソリューション構造の最適化

貪欲な選択的

アルゴリズムの複雑さ

まとめ

一般的なアルゴリズム

フレーム

基本的な考え方

アルゴリズムの説明

貪欲な選択性

意味

カット(S、V-S)

クロスカット

刃先セットAに準拠

カットのライトエッジを越えて

定理1

Kruskal: A [一連の接続されたコンポーネントを含む] に続くカット全体のライトエッジと、A に含まれないポイントを見つけます。

プリムのアルゴリズム

レビュー

最小完了時間 5.5 最小マックスパンスケジューリング

問題定義

近似アルゴリズム

パフォーマンス分析

第6章償却分析

基本的

基本的な考え方

スタック操作: データ構造と操作間の関係を無視します。

償却分析法

目的: 特定のデータ構造に対する n 回の操作のコストの上限を分析する

各操作のコストは、合計コスト [上限] を通じて均等に分析されます。

決定されるのは確率ではなく上限です

集計方法

平均

会計方法

前払い [データオブジェクトに関連付けられた、データオブジェクトのクレジット]

位置エネルギー法

蓄積されたポテンシャル [データ構造全体、エネルギーに関連する]

集計方法

分析する

分析过程中要精细化，注意每个操作之间的关联

用数据对象上小的操作代价来来预付之后的大的操作代价