복잡도(Complexity)
복잡도는 알고리즘의 성능을 나타내는 척도이다.•
시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
•
공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 빅오 표기법•
가장 빠르게 증가하는 항만을 고려하는 표기법이다.
•
함수의 상한만을 나타낸다. 즉 차수가 가장 큰 항만 남긴다.
•
위로 갈수록 좋다.
순위 | 명칭 | |
상수 시간 (Constant time) | 몇번의 연산만 거치면 수행 완료되는 경우 | |
로그 시간 (Log time) | logN 에 비례하는 만큼 수행이 된다. | |
선형 시간 (Linear time) | ||
로그 선형 시간 | ||
이차 시간 | ||
삼차 시간 | ||
지수 시간 |
•
시간 복잡도 계산해보기
[예제 코드 1]
array = [3, 5, 1, 2, 4]
summary = 0
for x in array :
summary += x
print(summary)
Python
복사
수행 시간은 데이터의 개수 5 에 비례할 것임을 예측할 수 있다.
따라서 시간 복잡도는 이다.
[예제 코드 2]
array = [3, 5, 1, 2, 4]
for i in array :
for j in array :
temp = i * j
print(temp)
Python
복사
시간 복잡도는 이다.
모든 2중 반복문의 시간 복잡도가 인 것은 아니다. 소스 코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도 까지 고려해야 한다.
알고리즘 설계 Tip
일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘기는 경우 : •
통상 5 ~ 15 초 가량의 시간이 소요된다.
•
PyPy 의 경우 때때로 C 언어 보다 빠르게 동작하기도 한다.
코딩 테스트에서 시간제한은 통상 1 ~ 5 초 가량이다. 요구사항에 따라 적절한 알고리즘 설계하기•
문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항) 이다.
•
시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.
◦
N 의 범위가 500 인 경우 : 시간 복잡도가 인 알고리즘을 설계하면 문제를 풀 수 있다.
◦
N 의 범위가 2000 인 경우 : 시간 복잡도가 인 알고리즘을 설계하면 문제를 풀 수 있다.
◦
N 의 범위가 100000 인 경우 : 시간 복잡도가 인 알고리즘을 설꼐하면 문제를 풀 수 있다.
◦
N 의 범위가 10000000 인 경우 : 시간 복잡도가 인 알고리즘을 설계하면 문제를 풀 수 있다.
일반적인 알고리즘 문제 해결 과정•
지문읽기 및 컴퓨터적 사고
•
요구사항(복잡도) 분석
•
문제 해결을 위한 아이디어 찾기
•
소스코드 설계 및 코딩
•
일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제합니다.
수행시간 측정 소스코드 예제import time
start_time = time.time()
##############################
end_time = time.time()
print("time:", end_time - start_time)
Python
복사