알고리즘 성능 분석 : 시간 복잡도 & 공간 복잡도

이미지 출처 : https://heekim0719.tistory.com/266

 

 

1. 시간 복잡도 (Time Complexity)

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지
• 알고리즘 실행을 위해 필요한 연산의 횟수 (시간)
• 빅오 표기법 (Big-O) 사용
• 코딩 테스트에서 [시간 제한 n초]에서 고려해야 함

 

2. 공간 복잡도 (Space Complexity)

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지
• 알고리즘을 위해 필요한 메모리의 양 (공간)
• 빅오 표기법 (Big-O) 사용
• 코딩 테스트에서 [메모리 제한 n MB]에서 고려해야 함

 

3. 빅오 표기법 (Big-O Notation)

• 가장 빠르게 증가하는 항 만 고려하는 표기법
• ex. 3n^3 + 2n^2 + 10000 일 때의 시간 복잡도 : Big-O : O(n^3)

시간 복잡도 표

• 아래 그림에서 알고리즘은 오른쪽으로 갈 수록 오래 걸리며 성능이 나쁘다.

알고리즘 성능 비교

• 코딩 테스트에서는 본인이 짠 알고리즘이 일반적으로 O(n^3)을 넘어가면 문제 풀이에서 사용하기 어려움

 

// Kotlin

fun main() {
    val list = listOf(3, 5, 1, 2, 3)
    var sum = 0

    for (index in list) {
        sum += index
    }

    println(sum)    
}

• list에 5개의 정수가 있음 (N = 5)
• for문을 통해 list안에 있는 데이터를 차례로 검사 후 더하는 알고리즘
• 연산의 횟수는 N에 비례함
• 시간 복잡도 : O(n)
• 이 때, N이 커짐에 따라 영향을 받는 부분은 for문임을 알 수 있다.

 

// Python

array = [1, 3, 4, 5, 7]

for i in array:
    for j in array:
        value = i * j
        print(value)

• array에 5개의 정수가 있음 (N = 5)
• 이중 for문으로 데이터를 검사 후 곱하는 알고리즘
• 연산의 횟수는 N * N만큼 필요
• 시간 복잡도 : O(n^2)
• 모든 이중 for문이 O(n^2)는 아니다
  • for문 안에서 어떤 함수를 call하는 경우에 해당 함수의 시간 복잡도 까지도 고려해야한다.
  • 하지만, 대체적으로 이중 for문의 시간 복잡도는 O(n^2)이다.

 

Reference

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC