7주차, 시간복잡도

O(1)

・ 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘

    ・ 배열의 Random Access 

    ・ Hash

 

O(N)

・ 입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘

 

for (int i = 0; i < N; i++){

    // for 가 O(N)의 시간복잡도를 가진다.

}

 

O(N^2)

・ 입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘

 

for (int i = 0; i < N; i++){

    for (int i = 0; i < N; i++){

        // 중첩 for문은 O(N^2)의 시간복잡도를 가진다.

    }

}

 

O(logN)

・ 이진탐색(Binary search) // 가장 효율적인 up down과 같음, 한 번 연산할 때마다 연산범위가 반으로

 

・ n, n/2, n/4, ... , (1/2)^kn 

・ (1/2)^kn ≈ 1      // ≈ == ≒ == 근사치

・ n ≈ 2^k

 

・ logn ≈ K     // K는 시행횟수

 

O(NlogN)

・ Merge sort // 주어진 데이터 집합 중 절반씩 나누는 과정을 먼저 하고, 하나씩 값을 비교하며 다시

// 정렬하는데 입력 개수인 N번만큼 정렬한다.