[알고리즘] 복잡도 / 빅오 표기법 기본 개념

1. 복잡도(Complexity)

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석

동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 복잡도가 높다라는 것은 특정한 함수의 성능적인 측면에서 많은 시간을 소요하고, 많은 메모리의 자원을 먹는 것을 말한다.

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

http://bigocheatsheet.com/

• 가장 빠르게 증가하는 항(최고차항)을 고려하는 표기법
• 함수의 상한(최악의 수행시간)만을 나타내게 된다.

ex ) 3N² + 5N + 100 의 경우, 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N²)으로 표현된다.

일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우 코딩 테스트 문제에서 시간 제한은 통상 1 ~ 5 초 가량 ( 명시되어 있지 않은 경우 대략 5초가 대부분 )

3. 요구사항에 따라 적절한 알고리즘 설계하기

시간 제한(수행시간 요구사항) : 문제에서 가장 먼저 확인해야하는 내용으로 시간제한이 1초인 문제를 만났을때 가정하며, 일반적의 기준으로는 다음과 같다.

1. N의 범위가 500인 경우 : 시간 복잡도 O(N³)인 알고리즘 설계 가능
2. N의 범위가 2,000인 경우 : 시간 복잡도 O(N²) 인 알고리즘 설계 가능
3. N의 범위가 100,000인 경우 : 시간 복잡도 O(NlogN)인 알고리즘 설계 가능
4. N의 범위가 10,000,000인 경우 : 시간 복잡도 O(N)인 알고리즘 설계 가능

4. 알고리즘 문제 해결 과정

1. 지문 읽기 + 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩
   

5. 수행시간 측정 소스코드 예제 ( python 라이브러리 )

import time

start_time = time.time() # 측정 시작

# 프로그램 소스코드

end_time = time.time() # 측정 종료

print("time:", end_time - start_time) # 수행 시간 출력

---

참조

1. 이것이 코딩테스트다

2. https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기