今日やったこと

データ構造/アルゴリズムの時間複雑度の概念を理解した.
Greedアルゴリズム,動的プログラミングの概念を理解した.

Achievement goals

アルゴリズムとは何かを説明することができます.

の時間的複雑さについて説明することができる.

アルゴリズム(Algorithm)

コードstaitsでいうアルゴリズムは、「問題をどのように解決するかが最善」と定義されています.
私が理解したように,前述したDFS BFSのグラフィックでの巡回目的は同じであるが,方法は異なる.
いかなる問題も深く理解し、さまざまな問題をより効率的に解決する方法を考えます.
これは最良の戦略を立てる練習のようだ.

時間の複雑さ

問題を解決する際により効果的な方法を考えるのは、時間の複雑さを考慮することに等しい.
時間の複雑さは入力値の増加/減少に伴って増加/減少します.そう言えば、
以前のソリューションでは、
このアルゴリズムは,入力値が大きくなるにつれて増加する時間パーセンテージが最小となるアルゴリズムを構成していると考えられる.
今日学んだ時間的複雑さは最もよく用いられるBig−Oマーキング法である.
O(1):データの大きさにかかわらず,常に一定時間のアルゴリズムが必要である.

function O_1_algorithm(arr, index) {
	return arr[index];
}

O(n):データサイズが増加するにつれて、時間も同じ割合で増加するアルゴリズム.

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

O(logn):Big−Oマーキング法ではO(1)に次ぐ高速時間複雑度であり,代表的なものはバイナリ探索アルゴリズムである.
バイナリ検索とは,処理を行うたびに検索するデータ量を半分に減らすアルゴリズムである.

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
		}
	}
}

O(2^n):Big-Oマーキング法で最も遅い時間複雑度.nの2勝と混同されるかもしれないが,この2つのアルゴリズムは全く異なる.これは,入力されたデータが大きいほど時間が2の二乗増加するアルゴリズムである.
最も代表的な復帰が現れるフィボナッチ数列は、nを100以上にしても一生の結果は得られないという.

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

コメントサイト

https://www.youtube.com/watch?v=6Iq5iMCVsXA