복잡도 (Complexity)

복잡도는 알고리즘의 성능을 나타내는 척도이다.

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

동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

시간 복잡도

시간 복잡도를 표현할 때는 주로 빅오 표기법(Big-O Notation)을 사용한다.

빅오 표기법 (Big-O Notation)

가장 빠르게 증가하는 항만을 고려하는 표기법이다.

• 함수의 상한만을 나타낸다.

예를 들어, 연산 횟수가 $3N³ + 5N² + 1,000,000$인 알고리즘이 있다고 하자.

• 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 $O(N³)$으로 표현된다.

아래는 시간 복잡도 표인데, 위쪽에 있을수록 더 빠르다.

시간 복잡도 계산해보기 1)

• N개의 데이터의 합을 계산하는 프로그램 예제

array = [3, 5, 1, 2, 4] # 5개의 데이터 (N=5)
summary = 0 # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary += x

# 결과를 출력
print(summary)

• 수행 시간은 데이터 개수 N에 비례할 것임을 예측할 수 있다.
  • 시간 복잡도 : $O(N)$

시간 복잡도 계산해보기 2)

• 2중 반복문을 이용하는 프로그램 예제

array = [3, 5, 1, 2, 4] # 5개의 데이터 (N=5)

for i in array:
	for j in array:
    	temp = i * j
        print(temp)

• 시간 복잡도 : $O(N²)$
• 참고로 모든 2중 반복문의 시간 복잡도가 $O(N²)$인 것은 아니다.
  • 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 한다.

알고리즘 설계 Tip ❗

• 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:
  • C언어를 기준으로 통상 1 ~ 3초 가량의 시간이 소요된다.
  • Python을 기준으로 통상 5 ~ 15초 가량의 시간이 소요된다.

    만약 Python으로 최대한 효율적으로 짰는데도 불구하고 시간 초과가 난다면 PyPy로 변경하여 제출해보기!

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

• 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)이다.
• 시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.
  • N의 범위가 500인 경우 : 시간 복잡도가 $O(N³)$인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 2000인 경우 : 시간 복잡도가 $O(N²)$인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 100,000인 경우 : 시간 복잡도가 $O(NlogN)$인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 10,000,000인 경우 : 시간 복잡도가 $O(N)$인 알고리즘을 설계하면 문제를 풀 수 있다.

계속 이렇게 생각해서 문제 풀기

알고리즘 문제 해결 과정

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

• 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제한다.

수행 시간 측정 소스코드 에제

• 일반적인 알고리즘 문제 해결 과정은 다음과 같다.

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

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

[References]
이것이 코딩테스트이다 with 파이썬 책을 참고하였습니다.
https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98