알고리즘의 성능

시간복잡도

• 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

공간복잡도

• 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

시간복잡도와 공간복잡도가 낮은 코드가 매우 효율적인 코드다!

빅오 표기법

• 가장 빠르게 증가하는 항만을 고려해 표현한 표기법!

ex) 3N^3 + 5N^2 + 1,000,000의 연산 횟수를 가진 알고리즘이 있다. 빅오 표기법에서는 가장 빠르게 증가하는 항만 남기므로 시간복잡도가 O(N^3)인 알고리즘! 이라고 표현할 수 있겠다.

시간복잡도의 효율 순서(아래로 내려갈수록 효율이 낮음)

• O(1) -> 상수 시간
• O(logN) -> 로그 시간
• O(N) -> 선형 시간
• O(NlogN) -> 로그 선형 시간
• O(N^2) -> 이차 시간
• O(N^3) -> 삼차 시간
• O(2^n) -> 지수 시간

ex)

arr = [1, 2, 3]
sum = 0

for x in arr:
	sum += x
print(sum)

• 위는 N개의 데이터의 합을 계산하는 식이다. 이 때, 계산해야하는 수의 범위는 arr의 데이터 갯수가 증가할수록 커지므로 O(N)의 선형 시간을 가진다는 것을 알 수 있다. 3개의 데이터는 O(3), 100개의 데이터는 O(100)으로 증가하는 방식이다.

ex2)

arr = [1, 2, 3]

for x in arr:
	for j in arr:
    tmp = i *j
	print(tmp)

• 위의 경우엔 for문으로 j가 3만큼 순회할 때마다 i가 증가해 총 9번의 연산을 한다. 그래서 데이터의 개수(3)^2만큼의 복잡도를 가지므로 O(N^2) 이차 시간의 시간복잡도를 가진다.
• 만약 이중 반복 이외에 또 다른 함수나 연산이 이루어지면 더욱 비효율적인 시간복잡도를 가질 수 있다!

시간제한 확인하기

• 시간제한이 1초인 문제가 주어진다면,
  • N의 범위가 500 : O(N^3)인 알고리즘으로 풀 수 있다.
  • N의 범위가 2,000 : O(N^2)인 알고리즘으로 풀 수 있다.
  • N의 범위가 100,000 : O(NlogN)인 알고리즘으로 풀 수 있다.
  • N의 범위가 10,000,000 : O(N)인 알고리즘으로 풀 수 있다.

알고리즘 해결 과정

1. 지문 읽고 컴퓨팅적 사고

2. 요구사항(복잡도, 시간제한, 공간제한 등..) 분석

3. 문제 해결 아이디어 스케치

4. 소스코드 설계 및 구현

출처: 동빈나님 알고리즘 유튜브