코딩테스트를 위한 복잡도와 빅오 표기법

복잡도 : 알고리즘의 성능을 나타내는 척도, 일반적으로 낮을수록 좋은 알고리즘

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

 

 

빅오 표기법 : 가장 빠르게 증가하는 항(함수의 상한)만을 표기

O(1) < O(logN)  < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^n)

num = [1,2,3,4]
sum = 0

for i in sum:
	sum+=i
 
print(sum)

# 수행 시간은 데이터의 개수 N에 비례하므로 시간 복잡도는 O(N)

arr = [1,2,3,4]

for i in arr:
	for j in arr:
    	sum += i+j
print(sum)

# 시간 복잡도: O(N^2)
# 모든 2중 for문의 시간 복잡도가  O(N^2)인것은 아니며, 다른 함수를 호출한다면 그 함수의 시간 복잡도도 고려

 

 

 

일반적으로 연산 횟수가 5억을 넘어가는 경우 python은 5~15초 가량의 시간이 소요
코테의 일반적인 시간제한은 1~5초라는 것에 유의 하여 알고리즘 짜는것이 좋다.
python으로 제출하고 시간초과 판정을 받는다면 pypy로 바꿔서도 제출해보자. (종종 c 보다도 빠르게 동작)

 

 

 

 

요구사항에 따라 알고리즘 설계 하는 법

: 문제에서 가장 먼저 확인해야 하는 내용은 시간제한이며, 1초인 경우는 일반적으로 아래와 같다.

• N의 범위가 500 : O(N^3)인 알고리즘을 설계
• N의 범위가 2000 : O(N^2)인 알고리즘을 설계
• N의 범위가 100,000 : O(NlogN)인 알고리즘을 설계
• N의 범위가 10,000,000 : O(N)인 알고리즘을 설계

 

 

일반적인 알고리즘 해결 과정

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

 

 

수행 시간 측정 소스 코드

import time

start_time=time.time()

# 소스코드 시작
#
# 소스코드 끝

end_time = time.time()
print(end_time - start_time)