この文章はせつぞくせんのアルゴリズムの定義課程の受講と総括である.
不正確な内容や漏れがある場合がありますので、講義をお勧めします.

1.評価基準：時間と空間

時間:できるだけ早く仕事を完成したいです.

空間:コンピュータの記憶空間(メモリの少ないプログラムに適している)

メモリにはコストがかかりますが、時間はありません.そのため、2つの評価基準では、時間がより重要です.

2.時間の複雑さ

データが多ければ多いほど、必要な時間が長くなります.
入力サイズアルゴリズムAアルゴリズムB 10個10秒10秒20個20秒40秒100個100秒1000秒
表1.アルゴリズムの時間的複雑さ
アルゴリズムAは?時間の複雑さが小さい→より速いアルゴリズム
アルゴリズムBは?時間複雑度が大きい→より遅いアルゴリズム

3.反復二乗と対数

繰返し二乗

23 = 2×2×22\times2\times22×2×2 = 8
22 = 232\frac{2^3}{2}223​ = 82\frac{8}{2}28​ = 4
212^121 = 222\frac{2^2}{2}222​ = 42\frac{4}{2}24​ = 2
202^020 = 212\frac{2^1}{2}221​ = 22\frac{2}{2}22​ = 1
2-1 = 202\frac{2^0}{2}220​ = 12\frac{1}{2}21​

ログ＃ログ＃

log⁡ab=x\log{_a}{b} = xloga​b=x →\rightarrow→ ax=ba^x = bax=b
aはいくら乗じてbを出すことができますか.
つまり、bをaで何回割ったら1に等しいのでしょうか.
計算機アルゴリズムではa=2の場合が多い.このとき「bは何回半に切ると1が出ますか?」そう思ってもいいです.
log28=3→23=8log{_2}{8} = 3\rightarrow 2^3=8log2​8=3→23=8
log327=3→33=27log{_3}{27} = 3\rightarrow 3^3 = 27log3​27=3→33=27
8を2で割ると3回で1、27を3で割ると1になります.
また、a=2 a=2 a=2であれば、loglog{a}{n}loganをlglg{n}lgnに書き込む.

4.1からnまでの和

  T = 1 +  2    +   3   + ... + (n-2) + (n-1) + n
+ T = n + (n-1) + (n-2) + ... +   3   + 2    +  1
--------------------------------------------------
 2T=(n+1) (n+1) (n+1)           (n+1)  (n+1)  (n+1)

2T = n*(n+1)
T =  n*(n+1)/2   # 1부터 n까지의 합

5.漸近線表記法

リスト長n[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]アルゴリズムに時間がかかる

20n+4020n + 4020n+40

2n2+8n+1572n^2 + 8n + 1572n2+8n+157

20lg⁡n+6020\lg{n} + 6020lgn+60

これらの数字は、コンピュータのパフォーマンスやプログラミング言語などの環境要因に依存します.(数式だけではアルゴリズムに必要な時間を完全に表現することはできません.)
そこで、コンピューター科学者たちはアルゴリズムを評価する方法で「漸近マーキング法」を提案した.
時間漸近マーキング法(Big−O)20 n+4020 n+400 n+400 n+40 O(n)O(n)2 n 2 n 2+1572 n+157n 2+8 n 2(n 2)O(nn2)O(n 2)O(n 2)O(n 3)、n 3+100 n 2、n 2、n 2、n 3、n 3、n 3、n 3、n 3、n 3、n 3、n 2、n 2、n 2、n 2、n 3、n 3、n 3、n 3、n 3、n 3、n 3、n 3、n 3、O(n 3)O(n 3)O(n 3)O(n 3)O(n 3)O(n 3)O(n 3)O(n 3)O(n 3)O(n 3)O(n(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n))O(n)O(lg{n})O(lgn)
表2.漸近シンボルの例

漸近マーキング法のコア

n最も影響力のある場所を探し、残りは

を削除します.

n前の数字を削除します.

なぜ漸近マーキング法を使うのですか?

私たちが関心を持っているのは絶対的な時間ではなく、成長性です.
漸近マーキング法の核心はnが大きいと仮定することである.
→nが大きくなければ、悪いアルゴリズムでも大丈夫です.

2 n 2+8 n+1572 n^2+8 n+1572 n+8 n+1572 n+8 n+1578 n+1578 n+1578 n+1578 n+1578 n+1578 n+1578 n+1578 n.
Input size(以下、nと略す)が大きいほど、グラフィックの傾斜差が大きくなり、n=10000の場合、時間値は1時間当たり2兆、800万(垂直軸)となる.下図に示すように、nは、8 n+1578 n+1578 n+1578000 n+1578000 n+1578000 n+1578000 n+1578000 n+1578 n+1578 n+1578 n+1578 n+157800 n+157800 n+157800 n+157800 n+157800 n+1578 n+1578 n+1578 n+1578 n+1578 n+重要な影響を及ぼす2 n^2以外は無視できると結論した.
従って、nの影響力が最も大きい場所(2 n 2+8 n+1572 n^2+8 n+1572 n+8 n+157~2 n 22 n^22 n 2)を見つけ、残りの削除の最初のコアを見つけた.

2 n 2+8 n+157→0.01 n 2+8 n+1572 n+1572 n+1572 n+1572 n+1572+1572+1572→0.01 n 2+8 n+157右向き矢印0.01 n^2+8 n+1572 n+1572→0.01 n 2+8 n+157、修正して比較しても青の直線がオレンジの直線を越えるタイミングは異なります.最後にn 2 n^2 n 2であることが重要なので、「nの前の数字を削除します.」これにより、2番目のコアが引き出されます.

6.漸近表記法の意義

O(1),O(n),O(n),O(n^2)およびO(n^3)速度を持つ4つのアルゴリズムを比較した.
n(例えば入力リストの長さ)O(1)O(1)O(1)O(1)O(1)アルゴリズム所要時間O(n)O(n)O(n)O(n^2)O(n 2)アルゴリズム所要時間O(n 3)O(n^3)アルゴリズム所要時間1001秒1秒2001秒2秒8秒10001秒10秒1000秒1,000秒1,000秒100000秒
表3.アルゴリズム比較

異なる環境でのアルゴリズムの比較

他の環境で実行しても、アルゴリズムが悪いと最終的には多くの時間がかかります.
n(例えば、入力リストの長さ)O(1)O(1)O(1)O(1)O(1)O(1)アルゴリズム所要時間O(n)O(n)O(n)O(n^2)O(n 2)アルゴリズム所要時間O(n 3)O(n^3)アルゴリズム所要時間10010秒1秒0.01秒20010秒0.48秒100010秒10秒10秒10秒10秒10秒10秒1000秒10000秒
表4.異なる環境でのアルゴリズムの比較

7.ナビゲーションアルゴリズムの評価

# 선형탐색 평가하기
def linear_search(element, some_list):
    i = 0  # O(1)
    n = len(some_list) # O(1)

    while i < n:  # O(1) x 반복횟수(n)
        if some_list[i] == element:
            return i
        i += 1

    return -1  # O(1)

最適:O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)=O(4)=O(1)+O(1)+O(1)+O(1)+O(1)+O(1)=O(1)=O(1)=O(1)=O(1)=O(1)
最悪:O(1)+O(1)+O(1)+O(n)+O(1)=O(n)O(1)+O(1)+O(n)+O(1)=O(n+3)=O(n)O(1)+O(1)+O(1)+O(1)+O(1)=O(n+3)=O(n)

def binary_serach(element, some_list):
    start_index = 0  # O(1)
    end_index = len(some_list -1) # O(1)

    while start_index <= end_index:  # O(1) x 반복 횟수 (lg n)
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif element < some_list[mid_point]:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1

    return None  # (1)

最適:O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(1)=O(4)=O(1)+O(1)+O(1)+O(1)+O(1)+O(1)=O(1)=O(1)=O(1)=O(1)=O(1)
最悪の場合、O(1)+O(1)+O(1)+O(1)=O(lg⁡n+3)=O(1)+O(1)+O(1)+O(1)+O(1)=O(lg{n}+3)=O(lg)+O(1)+O(1)+O(lgn+O(1)

8.アルゴリズム評価の注意事項

漸近マーキング法ではnは?
フィートの大きさを表す

でよく使われる文字は、特に意味がありません.他の文字で表してもいいです.

コードのすべての行はO(1)ですか?

のフィートサイズと実行されないコードだけがO(1)である.

operationCodeAvarage Caseインデックスmy list[index]O(1)ソートmy list.sort()sorded(my list)O(nlgn)my listを反転します.my listo(n)の末尾に要素reverse()O(n)ナビゲーション要素my listを追加します.append(要素)O(n)の間に要素myリストを追加します.Insert(index,element)O(n)delmy list[index]O(n)の最切り上げを削除し、最値min(my list)max(my list)O(n)len(my list)O(1)スライドmy list[a:b]O(b-a)を検索する
表5.List Operations
OperationCodeAvarage Case値my dict[key]O(1)プラス/上書きmy dict[key]=valueO(1)値を検索delmy dict[key]O(1)を削除
表6.Dictionary Operation

9.主な時間複雑度のまとめ

時間複雑度は、アルゴリズムの実行時間が入力サイズに比例することを示す.
O(1)O(1)O(1):入力の大きさは所要時間に影響しない.
O(n)O(n)O(n):繰り返し文があり、繰り返し回数は入力の大きさに比例し、一般的にO(n)O(n)O(n)O(n)O(n)O(n)である.複文の個数によっては、O(3 n)O(3 n)O(3 n)などであってもよいが、3は破棄され、O(n)O(n)O(n)O(n)O(n)となると考えられる.
O(n 2)O(n^2)O(n 2):重複文が重なる場合(重複文の重複文)
O(n 3)O(n^3)O(n 3):3回繰り返す
O(lglg)O(lg)O(lg):繰り返しを実行するたびに、ステップが減少します.

# case 1
# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def print_powers_of_two(n): # n = 128일 때
    i = 1
    while i < n: # i=1, 2, 4, 8, 15, 32, 64까지 7회 실행된다.
        print(i)
        i = i * 2  # i의 값이 2배 씩 증가한다. 이 코드가 수행될 때마다 필요한 수행 단계가 줄어든다.

# case 2
# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def print_powers_of_two(n): # n = 128일 때
    i = n
    while i > 1: # i=128, 64, 32, 16, 8, 4, 2까지 7회 실행된다.
        print(i)
        i = i / 2  # i의 값이 반씩 나눠진다. 마찬가지로 필요한 수행단계가 줄어든다.

O(nlg)O(nlg)O(nlgn):O(n)O(n)O(n)とO(lg)O(n\lg)O(lgn)が重なる.

def print_powers_of_two_repeatedly(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

評価するにはコードが必要ですか?

コードレス評価アルゴリズムのテクニック
線形ナビゲーションを考慮すると、

の簡単なアルゴリズムの1つです.大まかに言えば,繰返し回数が最も悪い場合はnnnと考えられる.また,バイナリナビゲーションではリストが半分にカットされるので,最悪の場合,loglog{2}{n}log 2 nを思い出すかもしれない.では、以下のように考えることもできます.

「線形探索をするには最悪の場合n個を見なければならないのでO(n)O(n)O(n)~」
「バイナリ探索を行うには、最悪、このn個のログlog 2}{n}log 2 nを見なければならないので、lglg{n}lgn、つまりO(lglg)O(lg)O(lgn)~」

bigoマーキング法自体は、アルゴリズムの性能をざっとまたはざっと評価するために作成されたことを覚えておいてください.

の内部動作を頭で描けば、時間の複雑さを大体思い出すことができます.頭で計算する練習を続ける.

11.空間複雑度

スペース複雑度(Space Complexity)は、アルゴリズムが使用するメモリ領域が入力サイズに比例することを示します.

def product(a, b, c):
    """result의 공간은 인풋과 무관하기 때문에 공간 복잡도는 O(1)"""
    result = a * b * c
    return result

def get_every_other(my_list):
   """인풋인 my_list의 크기는 every_other의 공간에 영향을 준다. O(n/2) -> O(n)"""
    every_other = my_list[::2]
    return every_other

def largest_product(my_list):
    """인풋인 my_list의 크기는 중첩된 반복문에 의해 products의 공간에 영향을 준다. O(n^2)"""
    products = []
    for a in my_list:
        for b in my_list:
            products.append(a * b)
    
    return max(products)