Big-O notation

4066 ワード
アルゴリズム#アルゴリズム# algorithm テキストリンク

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
    • Test Double(Test Double)Mock VS Stubの理解
    linuxでのrtoの設定とrtoテスト