Big-O notation

アルゴリズムの効率タグ方法の1つ.

時間の複雑さ:実行速度.Nの大きさを入力するのに要する時間によります.

スペースの複雑さ:使用するメモリの量.

時間の複雑さを表すときに最も高いサブ港湾マーク.

インボリュートマークほう

ω記号:最適運転時間

プラグタワー記号θ Notation):平均運転時間

大書き方:最悪運行時間

時間の複雑さ

O(1):一定時間、一歩一歩問題を解決します.

O(log N):ログ時間(Logithmic)が減少し、トラブルシューティングに必要なステップが特定の要因によって減少します.

O(N):直線(Linear)時間、ステップ数は入力値nと1:1の関係にあり、問題を解決する.

O(N log N):線形ログ、Nlog Nであり、トラブルシューティングのためのステップ数はN(log 2 N)である.

O(N^2):二次(象限)時間、故障診断ステップ数は入力値Nの二乗

である

O(2^N):指数時間(Exponential)、故障診断ステップ数は所定の定数CのN二乗

である.
Complexity110100O(1)111O(log N)025O(N)110100O(N log N)020461O(N^2)110010000O(2^N)110241267650600228229401496703205376O(N!)13628800は表現できません

O(1): Constant

入力に関係なく、複雑さは同じです.

def sayHello():
    print("hello world")
    
def sayHi():
	print("hello world")
    print("hello world")
 
# 두 method의 복잡도는 똑같음

O(N): Linear

入力が増加するにつれて,時間と空間の複雑さも線形に増加した.

def sayHello(n):
    for _ in n:
    	print("hello world")

入力nを押して繰り返し文を実行します.

O(N^2): square

2回繰り返し,2回繰り返しn.

def sayHello(n):
	for x in n:
    	for y in n:
        	print(x,y)

O(log N)O(N log N)

所定の入力サイズで処理時間を増加させるソートアルゴリズムでは多く用いられる.

# 이진검색
def binary_search(n, item, first=0, last=None):
	if not last:
    	last = len(n)
    midpoint = (last-first)/2+first
    
    if n[midpoint] == item:
    	return midpoint
    elif n[midpoint] > item:
    	return binary_search(n,item,first,midpoint)
    else:
    	return binary_search(n, item,midpoint,last)

時間複雑度の例

O(1) time

配列インデックスの要素にアクセスします(int a=ARR[5];).

リンクリストにノードを追加します.

スタック/ポップアップにプッシュします.

キューの挿入/削除時.

arrayに格納されたツリーで、ノードの親ノードまたは左/右サブノードを検索します.

の二重リンクリストから次の/前の要素に移動した場合.

O(n) time

運転時間はnの入力サイズに比例する.

サイクルを使用して、要素のセットを繰り返します.

セットの半分以上を繰り返すと、O(n/2)->O(n)になります.

2つの異なるリングを用いて2つの個別の集合

:O(n+m)->O(n)

を繰り返す

Palindrome確認(i.g.yee、奥さん):逆順で読むのも同じです.

2つの

文字列を比較します.

線形検索:順番に検索します.linklistでよく使われます.

リンクリストの特定の要素を削除した場合(ソートされていません).

O(log n) time

実行時間は入力サイズのlogに比例します.

バイナリ検索:中間値からナビゲートを開始し、ツリー構造でよく使用されます.

バイナリ検索ツリーで、最小/最小値を検索します.

フィボナッチ数(Fibonacci numbers)計算:フィボナッチ数の1番目と2番目の値は1で、次からは前の数と前の数を加算する方法です.

O(n log n) time

実行時間は、入力サイズと入力サイズのlog積に比例します.

コレクションソート:O(n*log(n))を使用します.

Merge Sort.

Heap Sort.

Quick Sort.

O(n^2) time

実行時間は入力サイズの平方に比例します.
2つのネストリング

を使用して単一のセットを繰り返す場合:O(n)²).

2つのオーバーラップループ

を使用して2つの異なるセットを繰り返す場合:O(n*m)->O(n)²).

Bubble Sort.

Insertion Sort.

Selection Sort.

2 2 D配列ナビゲーション.

O(n!) time

すべてのシーケンスを生成します.
Ref:

https://www.bigocheatsheet.com/

https://towardsdatascience.com/introduction-to-big-o-notation-820d2e25d3fd

https://blog.chulgil.me/algorithm/

https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities