[ CS 50 ] 시간복잡도와 Big-O 표기법

시간 복잡도

시간 복잡도란 알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것입니다. 시간의 효율성이란 결국 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리 횟수가 적다는 의미이며, 연산자의 처리 횟수가 적다는 건 시간의 복잡도가 낮다는 의미입니다. 따라서 시간 복잡도가 낮을수록, 연산자의 사용 횟수가 적을수록 효율성이 높은 알고리즘이 됩니다.

 

Big-O 표기법

Big-O notation is a way of converting the overall steps of an algorithm into algebraic terms, then excluding lower order constants and coefficients that don’t have that big an impact on the overall complexity of the problem.

 

Big-O 표기법은 컴퓨터 과학에서 “대략”을 나타내는 공식적인 개념으로 최악의 경우에 대한 시간 복잡도를 나타내는 표현입니다. 

 

대표적인 시간복잡도 정의

1. O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.
   
   
2. O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
   
   
3. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.
   
   
4. O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
   
   
5. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.

선형 탐색은 비교적 간단한데 찾는 값이 배열의 맨 끝에 있는 최악의 상황의 경우 이 값을 찾는데 n번의 단계를 거치면 됩니다. 이 개념은 O(n)으로 나타납니다. 

버블 정렬에서는 인접해 있는 자료와 쌍을 이루어 비교하기 때문에, n개의 자료를 갖는 배열은 n-1쌍을 비교합니다. n개의 자료가 있을때 n-1번 비교해주면, n번째의 자료가 정렬되어있습니다. 그 이후로 n-1개의 자료를 다시 비교하게 됩니다. 전체 비교 횟수는 (n-1) + (n-2) + … + 1은 n(n-1)/2이며, n2n^2n2/2−n/2n^2/2 - n/2n2/2−n/2 로 나타낼 수 있습니다. 시간 복잡도는 가장 중요한(가장 지수가 큰) 부분만 남기고, 계수를 삭제합니다. 따라서 만약 n2/2−n/2 의 가장 중요한 부분은 n2/2이 되며 이것은 (1/2)n2입니다. 계수를 제외하면 n2이 남고 O( n2)으로 표현합니다.

 

선택 정렬은 가장 작은 값(혹은 가장 큰 값)을 찾아 제 자리를 찾아줍니다. n개의 자료가 있다면 첫 번째 자료와 나머지 n-1개의 자료 중 가장 작은 값의 자리를 교환해주어야 합니다. n-1개의 자료 중에서 가장 작은 값을 찾기 위해서는 n-1번의 비교가 필요합니다. 즉 비교 횟수는 버블 정렬과 마찬가지로 (n-1) + (n-2) + … + 1이며, 시간복잡도는 O( n2)으로 표현합니다.

 

삽입 정렬은 n개의 자료가 있다면 첫 번째 자료는 정렬이 되었다고 생각하고, n-1개의 자료 중 첫 번째 자료와 정렬된 자료를 비교합니다. 이때 정렬된 자료는 1개이기 때문에 비교 횟수는 1입니다. 정렬되지 않은 부분에 1개의 자료가 남게 되면, 정렬된 자료의 수 n-1개 만큼의 비교가 필요합니다. 따라서 비교 횟수는 1 + 2 + … + (n-1)이며, 시간복잡도는 O( n2)으로 표현합니다.

O(1) – 상수 시간

값을 검색할 때, 객체에서 키를 알거나 배열에서 인덱스를 알고 있으면 언제나 한 단계만 걸립니다.

// Constant time O(1)
func constantTime(_ n: Int) -> Int {
    let result = n * n
    return result
}

 

O(n) – 직선적 시간

// Linear time O(n)
func linearTime(_ A: [Int]) -> Int {
    for i in 0 ..< A.count {
        if A[i] == 0 {
            return 0
        }
    }
    return 1
}

O(LOG N) — LOGARITHMIC TIME (로그 시간)

배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듭니다.

// Logarithmic time O(log n)
func logarithmicTime(_ N: Int) -> Int {
    var n = N
    var result = 0
    while n > 1 {
        n /= 2
        print(n)
        result += 1
    }
    return result
}
logarithmicTime(128)

 

O(N^2) — EXPONENTIAL TIME (지수 시간)

지수 시간은 보통 문제를 풀기 위해 모든 조합과 방법을 시도할 때 사용됩니다.

// Quadratic time O(n^2)
func quadratic(_ n : Int) -> Int {
    var result = 0
    for i in 0 ..< n {
        for j in i ..< n {
            result += 1
        }
    }
    return result
}
quadratic(16)

 

Big Ω (omega) 표기법

 

Big-O와 비슷한 Big Ω (omega) 표기법이 있는데 Big Ω는 최선의 경우를 나타냅니다.

선형 탐색에서 최선의 경우는 배열의 처음에 찾고자 하는 값이 있는 상황입니다. 이는 배열의 크기와 상관없이 Ω(1)이라고 나타냅니다.

버블 정렬에서 최선의 경우(이미 정렬된 배열)를 생각해보면 버블 정렬은 교환이 이루어지지 않더라도 배열이 정렬된 사실을 모르기 때문에 여전히 n-1번의 비교를 해줘야 합니다. 그래서 최선의 경우는 Ω(n)로 표기합니다.

선택 정렬 역시 배열이 정렬되었다는 것을 알 수 없어, 최소값을 계속 찾아주어야 하므로 Ω(𝑛2n2 )로 표기합니다.

삽입 정렬은 정렬되지 않은 부분에서 정렬된 부분으로 옮겨갈 때, 정렬된 부분의 가장 큰 수와 비교하기만 하면 되기 때문에Ω(n)로 표기합니다.

---

본 게시물 코드

Algorithm/BigO/BigO.playground at main · Sheep1sik/Algorithm

---

출처

https://www.youtube.com/@cs50

https://www.edwith.org/cs50

https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/

https://www.udemy.com/course/the-swift-arcade-data-structures-and-algorithms-bootcamp/