［データ構造／アルゴリズム］1.Intro(時間複雑度)

1.良いアルゴリズムとは?

アルゴリズムとは?
これは

問題を解決する方法です.

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

の問題(速度が速く、メモリが少ない)を効果的に解決する方法です.

プログラム=データ構造+アルゴリズム

2.複雑度

データ構造の効率は、データ構造に対する演算の実行時間によって測定される.
実行時間を表す時間の複雑さとメモリ領域の大きさを用いる空間の複雑さに基づいて測定する
ほとんどの場合、パフォーマンスは時間的複雑さのみを使用して分析されます.

3.漸近線表記法

実行時間はアルゴリズムが実行する基本演算回数を入力サイズの関数として表す.
F(N)
これらの関数は多項式で表され、漸近記号を使用して入力サイズの関数として表されます.

3-1. 漸近マーキング法の種類

O(Big-O)表記法

Ω(Big-Omega)-符号

Θ(Theta)-マーキング法等

4.Big-O記号

result = 0
for i in range(n):
	result += i
print(result)

以上のコードは1からnまでのコードで、n回の演算を実行します
このコードの時間的複雑度はO(n)である.

result = 0
for i in range(n):
	for j in range(n):
		result += j
print(result)

result = 0
result2 = 0
for i in range(n):
	for j in range(n):
		result += j
for i in range(n):
	result2 += i
print(result + result2)

以上の2つのコードの時間的複雑度はいずれもO(N^2)である.

4-1. 最も一般的なBig-O

O(1):一定時間
入力値の大きさにかかわらず、

の運転時間は

である.

最適アルゴリズム

O(logn):ログ時間

運転時間は入力値の影響を受けるが、大きなnに対しても速い.

バイナリサーチアルゴリズム実行時間

O(N):線形時間
実行時間は、

入力値と比較して増加します.

O(Nlogn):ログ線形時間

ほとんどの効率的なソートアルゴリズムを実行する時間

に基づいて比較した並べ替えアルゴリズムがどんなに良いアルゴリズムでもO(nlogn)より速くはならない.

O(N^2):平方時間

低効率アルゴリズム(Bubbleソートなど)を実行する時間