アルゴリズムとは?
アルゴリズムは問題を解決する最良の選択である.
それぞれの状況の数を逐一比較し,その中から最適なものを選ぶ
また、ひとつひとつ比較しなくても、一番良さそうなものを先に見つけたら、後を無視することもあります
トラブルシューティング方法

問題を理解する
与えられた条件に基づいて、問題が何であるかを理解することから始まる.

問題を解決するための戦略を立てる
首都コードの作成
全体を描く

問題をコードに移す
戦略をコードに移行し、実装されたコードの最適化を試みる

時間の複雑さ

入力値の変化に応じて演算を実行する場合、演算回数に比べてどのくらいの時間がかかりますか?

入力値が大きいほど、増加時間の割合が最も小さいアルゴリズムは

である.

時間複雑度は主にbig-ohマーキング法で

を表す.

Big-O記号

Big-O

メガΩ

Big-θ

Big-Oマーキング法は最悪の場合を考慮しており,プログラムの実行に要する最悪の時間を考慮することができる.
「少なくとも時間がかかる」または「こんなに時間がかかる」に比べて、対応する応答を行うには"이 정도 시간까지 걸릴 수 있다"を考慮する必要があります.
計算時間よりも最悪の場合も考えた方が良いので、他の表記法よりもBig-O表記法の方が多く使われています.
Big-O記号は入力値の変化と比較して、演算を実行するのにどれくらいの時間がかかりますか?表示方法

O(1)

O(1)を定数複雑度と呼び、入力値が増加しても時間は増加しない、つまり、入力値の大きさにかかわらず、直ちに出力値を得ることができるO(1)時間複雑度を有するアルゴリズム

function O_1_algorithm(arr, index) {
	return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

上記のアルゴリズムでは,入力値の大きさにかかわらず,直ちに出力値を得ることができる.
たとえばarrの長さが100万であっても、すぐにインデックスにアクセスして値を返すことができます.

O(n)

O(n)は線形複雑度と呼ばれ、입력값이 증가함시간によれば同様の割合で増加することを意味する.
例えば、入力値が1の場合に1秒を要し、入力値を100倍にする場合に1秒の100倍を要する100秒を実現するアルゴリズムであれば、このアルゴリズムはO(n)の時間的複雑さを有するものといえるO(n)時間複雑度を有するアルゴリズム

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O n Algorithm関数では,入力値(n)を1つ増加するごとに,コードの実行時間が1秒増加する.
すなわち、入力値が増加するにつれて、同じ割合でかかる時間が増加する
関数のもう一つのO nアルゴリズムは,入力値を1つ増加するごとにコードの実行時間が2秒増加する
このアルゴリズムはO(2 n)と考えられる
しかし、実際にはこのアルゴリズムもBig-Oマーキング法でO(n)と表記されている.
入力値が大きいほど係数(n前の数)の意味(影響力)が色あせるので、同じ割合で増加すれば2倍ではなく5倍増加しても10倍増加してもO(n)で表す

O(log n)

O(log n)を対数複雑度と呼び,Big−Oマーキング法ではO(1)に次いで高速な時間複雑度を有する
BST(バイナリ探索ツリー)の値探索も論理的にO(logn)時間複雑度を持つアルゴリズム(探索方法)である.

O(n^2)

O(n^2)は二次複雑度と呼ばれ、入力値が増加するにつれて時間がnの平方数の割合で増加することを意味する.
例えば、入力値が1であれば、1秒を必要とするアルゴリズムに5の値を与え、25秒を必要とする場合、そのアルゴリズムの時間複雑度をO(n 2)と表すO(n^2)時間複雑度を有するアルゴリズム

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}
function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

2 n,5 nともにO(n)と表すように,n^3とn^5もO(n^2)と表す.
nが大きいほど指数の影響力は小さくなるので

O(2^n)

O(2^n)は指数複雑度と呼ばれ、Big-Oマーキング法において最も遅い時間複雑度を有する.
実装アルゴリズムの時間的複雑度がO(2 n)である場合,他の方法を考慮することが望ましい.O(2n)時間複雑度を有するアルゴリズム

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

再帰的に実現したフィボナッチ数列はO(2 n)時間複雑度をもつ古典的アルゴリズムである.
ブラウザ開発ウィンドウでは、nを40に設定しても数秒かかると判断できます.nが100を超えると、一生結果を返すことができない場合があります.
時間制限と所与のデータサイズ制限に基づいて時間複雑度を推定することが重要である
例えば、入力されたデータはnのサイズを有する.
nが100000未満の場合、O(n)またはO(nlogn)の時間的複雑度と予測され、プログラムが作成されるn^2の時間的複雑度が予測できない原因は,実数で推定できる.
1000000^2はすぐに処理するのが難しい数字(1000000*1000000=1000000)で、入力がn≦500に制限されている場合、O(n^3)の時間的複雑さを予測することができます
入力データが大きい場合は、O(n)またはO(log n)を満たす時間的複雑度を予測して問題を解くが、与えられたデータが小さい場合は、時間的複雑度が大きくても、問題の解き方に集中しなければならない.
時間の複雑さはデータのおおよその大きさによって決まる

Big−Oは上限漸近,Big−Ω(omega)は下限漸近,Big−Θ(theta)両者の平均値を表す

Greedy Algorithm

Greedyは「貪欲、貪欲」という意味で、Greedy Algorithm(貪欲アルゴリズム)は、選択した瞬間に、目の前の最良の状況だけを追求し、最終的な答えを達成する方法です.
貪欲なアルゴリズムで問題を解決する方法は以下のステップに分けることができる.
1.プログラムの選択:現在の状態でのベストアンサーの選択
2.適切性検査:選択した解が問題の条件を満たすかどうかを検査する
3.解答検査:元の問題が解決したかどうかを検査し、解決していない場合、選択ステップに戻って、以上の手順を繰り返す
例1
お客さんが買い物をして小銭を探しているとき、
最小コイン数を得る方法
顧客:4040元のものを買って、5000元払った時
960元の小銭を探しています
500元のコインを一つ選びます.次に100円玉を4個選択し、50円玉と10円玉を1個ずつ選択します.

選択プログラム:おつりの硬貨数を減らすために、現在最も価値のある硬貨

を優先的に選択する.

適切性検査:1番の過程で選択した硬貨の和が取り戻した金額を超えているかどうかを検査し、超えたら最後に選択した硬貨を削除し、1番に戻って小さな硬貨

を選択する.

解答検査:選択した硬貨の和が取り戻した金額と一致するかどうかを検査し、金額が不足している場合は、第1のプロセスから

を繰り返す.탐욕 알고리즘は,問題を解決する過程で,毎時毎刻最適解(局所最適解)を探し,これに基づいて最終問題の解(グローバル最適解)を達成する問題解決方式である.
しかし、常に最良の結果を保証することはできないことを覚えておいてください.
したがって,2つの条件を満たす「特定の状況」でなければ,貪欲アルゴリズムは最適解を保証できず,貪欲アルゴリズムを適用して解決すべき問題は以下の2つの条件を備えなければならない.

貪欲選択属性:前の選択は後の選択に影響を与えない

最適部分構造:問題の最終解決方法は部分問題の最適解決方法からなる

欲張りアルゴリズムは必ずしも最適な結果を得ることはできないが,その利点はある程度迅速に最適な近似値を得ることができることである.
この利点は貪欲アルゴリズムを近似アルゴリズムとして使用できるようにした.
Github TILアルゴリズム