[추가] 복잡도

복잡도?!

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도

시간복잡도 + 공간복잡도

       시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 → 알고리즘을 위해 필요한 연산 횟수 측정 

       공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 → 알고리즘을 위해 필요한 메모리의 양 측정

       → 둘은 일종의 거래 관계가 성립함

       → 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하는 등

       → 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법을 '메모이제이션' 기법이라고 함

복잡도가 낮을수록 좋은 알고리즘

---

시간 복잡도 

알고리즘 문제 풀 때 단순히 '복잡도'는 시간 복잡도를 의미함

시간복잡도 표현 시 '빅오(Big-O) 표기법'을 사용함

       → 간단하게 정의하면, 가장 빠르게 증가하는 항만을 고려하는 표기법

       → 함수의 상한만을 나타냄

 

[예제]

1. O(N)

array = [3, 4, 2, 1] # N = 4
summary = 0

#모든 데이터를 하나씩 확인하며 합계를 계산 
for x in array: #array배열의 크기만큼 수행 
	summary += x

#결과 출력 
print(summary)

→ 위의 소스코드를 보면, 연산횟수는 N에 비례함

→ summary = 0 해주는 대입연산과 print() 해주는 출력연산도 있지만, 둘의 연산 횟수는 상대적으로 N이 커짐에 따라서 무시할 정도로 작아짐

→ 위의 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 for 반복문이므로 시간 복잡도는 O(N)

 

2. O(1)

a = 5 # 대입연산
b = 7 # 대입연산
print(a+b) #덧셈연산 + 출력

→ 대입연산과 출력함수를 제외하면 해당 소스코드의 연산 횟수는 1(더하기 연산 1번 수행)

→ 상수 연산이므로 시간 복잡도는 O(1)

 

3. O(N^2) 

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

#이중 반복문 
for i in array:
	for j in array:
		temp = i * j
		print(temp)

→ 해당 소스코드는 데이터의 개수(array 리스트의 크기)가 N개일 때, O(N^2)의 시간 복잡도를 가짐

주의사항) 모든 2중 반복문의 시간 복잡도가 O(N^2)는 아님. 만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 함. → 즉 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 함!

 

[시간복잡도 관련 주의사항]

→ 일반적으로 코테에서는 최악의 경우에 대한 연산 횟수가 가장 중요함 → 최악의 경우의 시간 복잡도를 우선적으로 고려해야 함

 

→ 차수가 작은 항들을 완전히 무시하는 것은 곤란함

            ex) 연산 횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘의 경우 빅오표기법으로는 O(N^3)으로 표기되지만,

                  실제로 N이 작을 때는 상수 값이 큰 영향을 미침

            → 일반적인 코딩 테스트에서는 상수를 고려해야 하는 경우는 적지만, 이처럼 빅오 표기법이 항상 절대적인 것은 아니라는 점 기억!!

→ 시간복잡도가 같더라도 알고리즘의 내부 로직 및 차수가 낮은 항의 영향에 따라 실제 수행되는 연산 횟수는 다를 수 있음

→ 보통 시간 복잡도에서의 '연산'은 프로그래밍 언어에서 지원하는 사칙연산, 비교연산 등과 같은 기본 연산을 의미함

 

[코딩 테스트에서 시간 복잡도의 의미]

→ 시간 복잡도 분석은 문제 풀이의 핵심

→ 문제의 조건을 먼저 확인하여 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 알 수 있음

→ 문제 풀 때 예시

 

---

시간 측정

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

...

end_time = time.time(); #측정 종료
print("time : ", end_time - start_time) #수행 시간 출력

→ 위의 코드를 통해 수행 시간 측정 가능함

 

참고) '이것이 취업을 위한 코딩테스트다' 책