시간 복잡도, 공간 복잡도, 빅오 표기법 간단 정리

시간복잡도

시간복잡도는 알고리즘이 주어진 입력 크기에 따라 문제를 해결하는 데 걸리는 시간의 상관관계를 나타내는 지표로, 입력 크기가 커질수록 알고리즘의 실행 시간이 어떻게 변하는지를 보여줍니다. 즉, 시간복잡도가 낮은 알고리즘일수록 더 효율적으로 문제를 해결할 수 있으며, 이는 알고리즘의 성능을 평가하는 중요한 기준이 됩니다.

 

 

시간복잡도 분석의 고려사항

1. 모든 상황을 고려

• 알고리즘의 성능을 평가할 때, 최선의 경우, 평균적인 경우, 최악의 경우를 모두 고려해야 합니다
• 대체로 최악의 경우로 가정하고 분석합니다

2. 입력값의 크기

• 입력값의 크기에 따라 알고리즘의 실행 시간에 미치는 영향을 고려해야 합니다.
• 일반적으로 입력값이 커질수록 실행 시간이 증가

이 외에 공간복잡도, 컴퓨터 성능 같이 여러 고려사항이 있지만 저는 일단 코딩테스트를 위해 해당 내용을 정리하고 있어서 서 해당 내용들은 다루지 않겠습니다.

 

 

시간복잡도 표기법

시간복잡도를 표현하는 표기법에는 빅-오메가(최선의 경우), 빅-세타(평균적인 경우), 빅-오(최악의 경우)와 같은 표현법이 있지만 최악의 경우를 고려하는 빅-오에 대해서만 알아보겠습니다. 빅-오 표기법은 다음과 같은 형태로 표현됩니다.

• O(1) - 상수 시간 (가장 빠름)
• O(lgN) - 로그 시간
• O(N) - 선형 시간
• O(NlgN) - 선형 로그 시간
• O(N²) - 이차 시간
• O(2^N) - 지수 시간
• O(N!) - 팩토리얼 시간 (가장 느림)

Big-O 복잡성 차트

출처: https://blog.encrypted.gg/922

이 차트는 빅-오 복잡성을 시각적으로 포현하여 입력 데이터의 크기에 따라 어떻게 변화하는지 보여줍니다. 예를 들어, O(1)는 입력 크기와 관계 없이 일정한 연산 수를 요구하는 반면, O(n!)은 입력 크기가 증가함에 따라 수행 시간이 기하급수적으로 증가하는 걸 볼 수 있습니다.

표기법	이름	설명	예시
O(1)	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가집니다.	배열에서 원소 하나 찾기
O(logn)	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가합니다.	이진 탐색
O(n)	선형 시간	입력 크기와 비례하는 실행 시간을 가집니다.	선형 탐색
O(nlogn)	선형 로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가합니다.	병합 정렬, 힙 정렬 알고리즘
O(n²)	이차 시간	입력 크기의 제곱에 비례하는 실행 시간을 가집니다.	선택 정렬, 버블 정렬
O(2^n)	지수 시간	입력 크기의 지수에 비례하는 실행 시간을 가집니다.	부분집합
O(n!)	팩토리얼 시간	입력 크기의 팩토리얼에 비례하는 실행 시간을 가집니다.	외판원 문제

 

공간복잡도

공간복잡도는 알고리즘에 입력의 크기와 문제를 해결하는데 필요한 공간(메모리 공간)의 상관관계입니다. 요즘 컴퓨터의 성능이 많이 좋아져서 공간복잡도 때문에 오류가 생기는 일은 별로 없습니다. 대신에 자료형의 크기 제한으로 인해 발생할 수 있는 Integer Overflow 문제를 피하기 위해 각 언어의 자료형에 따라 최솟값과 최댓값을 고려하여 코드를 작성하는 것이 중요합니다.

 

Java의 기본 자료형

int
크기: 4바이트 (32비트)
최솟값: -2,147,483,648
최댓값: 2,147,483,647

 

long
크기: 8바이트 (64비트)
최솟값: -9,223,372,036,854,775,808
최댓값: 9,223,372,036,854,775,807

 

short
크기: 2바이트 (16비트)
최솟값: -32,768
최댓값: 32,767

 

float

크기: 4바이트 (32비트)
최솟값: 약 -3.4028235E38
최댓값: 약 3.4028235E38

 

double
크기: 8바이트 (64비트)
최솟값: 약 -1.7976931348623157E308
최댓값: 약 1.7976931348623157E308

 

char
크기: 2바이트 (16비트, Unicode)
최솟값: '\u0000' (0)
최댓값: '\uFFFF' (65,535)

 

 

 

 

참고자료

https://blog.encrypted.gg/922

[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬