시간복잡도를 알아야 프로그램의 성능을 예측할 수 있다

아래는 피보나치 수열을 구하는 재귀함수이다.

def fibonacci(n)
	return 1 if n == 1
	return 1 if n == 2
	fibonacci(n-1) + fibonacci(n-2)
end

n = gets.chomp.to_i
puts fibonacci(n)

시간복잡도에 대해 어느정도 알고있다면, 위 코드의 성능이 상당히 나쁘다는 것을 바로 파악할 수 있다. 1초에 약 10억번의 연산을 한다고 가정했을 때, 해당 코드는 n의 크기가 대략 30 을 넘어서는 순간 1초 이상의 시간이 걸리게 된다. 이유는 해당 코드의 시간복잡도가 O(2^N)이기 때문이다.

반면 아래의 코드는 어떨까? 똑같은 피보나치 수열을 구하는 함수이다.

def fibonacci(n, a, b)
	return b if n == 1

	temp = a
	a = b
	b += temp
	fibonacci(n-1, a, b)
end

n = gets.chomp.to_i
puts fibonacci(n, 0, 1)

위 코드는 놀랍게도 n이 1000을 넘어가도 순식간에 답을 도출해낸다.

n = 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

이유는 해당 함수의 시간복잡도가 O(n)이기 때문.

실제로는 재귀 호출의 스택 한계로 인해 n의 값이 커지면 오류가 발생할 수도 있지만, 이론적인 시간복잡도 관점에서는 O(n)이므로 n=10억이 되어도 실행 시간은 1초 밖에 걸리지 않을 것이다.

이처럼 시간복잡도는 프로그램의 성능을 예측하고 이해하는데 큰 도움이 되는 도구이다.

확장 🌱

• O(n), O(2^n)에서 O의 의미가 무엇인가?
  • Big-Oh (최악의 경우를 나타낸다)
  • 최선의 경우와 평균을 의미하는 Omega, Theta도 있다.
• 시간복잡도 외 프로그램의 성능을 예측하는데 쓰이는 것이 있을까?
• 공간복잡도의 역할은? 시간복잡도만큼 성능에 크게 기여를 하는가?
• 재귀함수란?
  • 자기 자신을 호출하는 함수
• 재귀함수의 장점과 단점
• 모든 재귀함수는 반복문으로 재구현 될 수 있을까? 그 반대의 경우는?

관련 노트 📘

• 250512043750 - 배열의 삽입과 삭제에는 O(n)의 시간이 필요하다
• 250513050442 - 연결리스트의 경우 O(1)에 삽입 및 삭제가 가능하다
• 250518162405 - 시간복잡도를 안다고 해서 실제 성능을 예측할 수 있는 것은 아니다