복잡도(Complexity)

• 복잡도는 알고리즘의 성능을 나타내는 척도이다.
  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
• 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 예를들어 연산 횟수가 3N³ + 5N² + 1,000,000인 알고리즘이 있다고 할 경우.
  • 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N³)으로 표기한다.

시간 복잡도 계산해보기

1. N개의 데이터의 합을 계산하는 예제

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

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

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

2. 2중 반복문을 이용하는 예제

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

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

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