이것이 취업을 위한 코딩테스트다 With 파이썬
(코드는 Swift 기준으로 작성함)

복잡도 정의

  • 알고리즘의 성능을 나타내는 척도
  • 동일 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘
  • 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
  • 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양
  • 효율적 알고리즘은 시간-공간 복잡도 사이의 거래(Trade-off) 관계를 성립시킴
    - 메모리를 더 많이 사용해서 시간일 비약적으로 줄임 ... 메모이제이션 Memoization
    - 메모리(공간 복잡도)를 더 많이 사용하는 대신 반복연산(시간 복잡도) 생략

시간 복잡도

  • '복잡도'를 일컬을 때 대부분 시간 복자볻를 의미

빅오(Big-O) 표기법

  • 가장 빠르게 증가하는 항만을 고려해 나타내는 표기법
  • 차수가 가장 큰 항만 남겨 표기

표기법 종류

O(𝑵): 선형 시간 (N번 계산을 실행 ... 반복문)

let array = [1,2,3,4,5] // 5개의 데이터 (N=5)
var summary = 0

for x in array{
	summary += x
}

print(summary) // 15
  • 총 Summary에 더하기 연산을 5번(N번) 실행

O(1): 상수 시간 (단순 연산)

let a = 5
let b = 7
print(a+b) // 12
  • 연산은 단순 연산 a+b 한번만 이뤄짐

0(𝑵²): 이차 시간 (이중 반복문)

let array = [3,5,1,2,4]
var temp: Int

for i in array {
	for j in array{
    		temp = i*j
        	print(temp)
 	}
}
  • 이중 반복문이기 때문에 N * N 회의 연산을 수행하여 출력
  • 하지만, 모든 이중 반복문의 시간 복잡도가 O(N²)은 아님
    - 소스코드가 내부적으로 다른 함수를 호출하는 경우 내부 함수의 시간 복잡도 까지 고려해야 함

자주 등장하는 시간 복잡도 표

Big-O 표기법명칭
O(1)상수 시간
O(㏒𝑵)로그 시간
O(𝑵)선형 시간
O(𝑵㏒𝑵)선형 시간
O(𝑵²)이차 시간
O(𝑵³)삼차 시간
O(𝟤ⁿ)지수 시간
  • 위로 갈수록 빠른 복잡도

시간 복잡도 알고리즘별 연산 횟수

시간 복잡도 알고리즘N=1,000 기준 연산 횟수
O(𝑵)1,000
O(𝑵㏒𝑵)10,000
O(𝑵²)1,000,000
O(𝑵³)1,000,000,000

주의사항

  • 실제 코딩 테스트에서 차수가 작은 항들을 무시해서는 안된다
  • 예) 연산 횟수가 3𝑵³+5𝑵²+1,000,000인 알고리즘의 경우 가장 큰 차수만 남겨 O(𝑵³)겠지만 N=10과 같이 N의 값이 작은 경우 상수의 영향이 큼
    Big-O 표시가 무조건 절대적이지 않다는 것에 주의
  • 컴퓨터 과학에서는 시간 복잡도가 O(𝑁ᴷ): 다항 시간에 동작하는 알고리즘

문제 조건별 사용 알고리즘 분류 예시

  • 능숙한 숙련자들은 문제를 해석하기 전 조건(N의 범위)을 먼저 보고 사용할 알고리즘을 결정하기도 함

  • N의 범위가 클수록 알고리즘은 빠른 알고리즘으로 설계한다

  • 문제의 조건을 확인한 뒤 사용할 수 있는 알고리즘을 좁혀 나가는 전략 예시
    <조건(𝑵의 범위)별 설계 알고리즘 예시>

    𝑵의 범위설계할 알고리즘
    500O(𝑵³)
    2,000O(𝑵²)
    100,000O(𝑵㏒𝑵)
    10,000,000O(𝑵)

    공간 복잡도

  • 시간 복잡도와 똑같이 Big-O 표기법을 이용

  • 시간 복잡도가 1초라는 절대적 제한이 있는 것 처럼, 메모리는 MB 단위로 사용량 제한

    예시) 시간 제한 1초, 메모리 제한 128MB

  • 대부분 코딩테스트에서는 메모리 사용량을 128~512MB로 제한
    일반적으로 데이터의 개수가 1,000만 단위가 넘어가지 않도록 설계해야 함

시간과 메모리 측정

  1. 수행 시간 측정 소스 코드
let startTime = CFAbsoluteTimeGetCurrent() // 측정 시작

/* 코드 구현 */

let endTime = CFAbsoluteTimeGetCurrent() // 측정 종료

let durationTime = endTime - startTime  // 경과 시간
print("경과 시간: \(durationTime)") // 경과 시간 출력
  1. 수행 시간 비교 예시: 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교
import Foundation

// 배열에 10,000개의 정수 삽입
var array = [Int]()
for _ in 0..<10000 {
    array.append(Int.random(in: 1...100)) // 1에서 100까지 무작위 정수
}

// 선택 정렬 프로그램 성능 측정
var start_time = CFAbsoluteTimeGetCurrent()

// 선택 정렬 실행
for i in 0..<array.count {
    var min_index = i // 가장 작은 원소 인덱스
    for j in i+1..<array.count {
        if array[min_index] > array[j] {
            min_index = j
        }
    }
    var temp: Int
    temp = array[min_index]
    array[min_index] = array[i]
    array[i] = temp
}

var end_time = CFAbsoluteTimeGetCurrent()

print("선택 정렬 성능 측정: \(end_time-start_time)")

// 기본 정렬 위해서 배열 초기화
array = [Int]()
for _ in 0..<10000 {
    array.append(Int.random(in: 1...100)) // 1에서 100까지 무작위 정수
}

// 기존 정렬 라이브러리 성능 측정
start_time = CFAbsoluteTimeGetCurrent()

// 기본 정렬 라이브러리 실행
array.sort()

end_time = CFAbsoluteTimeGetCurrent()

print("기존 정렬 성능 측정: \(end_time-start_time)")
선택 정렬 성능 측정: 15.769272923469543
기존 정렬 성능 측정: 0.036099910736083984

=> 선택 정렬은 시간이 15초가 넘게 걸리고, 기본 정렬 라이브러리는 1초도 걸리지 않을 만큼 짧은 시간이 걸림
  • 선택 정렬은 시간 복잡도가 O(𝑵²)에 해당
  • 기본 정렬 라이브러리의 경우 시간 복잡도가 O(𝑵㏒𝑵)에 해당
  • 이에 따라 기본 정렬 라이브러리가 상대적으로 빠르다는 것을 알 수 있음

0개의 댓글