알고리듬 #10 적분으로 시간복잡도 구하기

알고리듬 공부를 하다가 보면 흔히 그냥 시간복잡도는 그렇구나 근데 왜 그렇게 되지?에 대해선 별로 민감하지 않다.

나 또한 그렇다, 시간복잡도가 그냥 대충 절반씩 줄면 log단위겟구나, 반복문 중첩이 많을 수록 제곱 되는구나 식으로 넘어갔지 

O(Nlog(logN))과 같은 시간복잡도가 왜 나오는지에 대해 궁금하지 않았다.

이번 글에서는 이런 시간복잡도를 적분을 통해 구하는 방식에 대해 소개한다.

적분 : 연속된 구간의 면적(누적량) 구하기

적분은 미분과 다르게 순간 변화율에 의해 실제로 변한 수치를 연속적으로 누적한 결과이다. 

시간복잡도와 적분: 합을 면적으로 근사하기

보통 시간복잡도는 반복문의 총 비용을 다음과 같이 시그마를 통해 합으로 쓴다.

이 합을 막대들의 합(리만 합)으로 보고 곡선 y=g(x) 아래 면적(정적분) 으로 근사하면, 총 작업량의 차수(Θ) 를 빠르게 읽어낼 수 있다.

즉, 적분을 통해 면적을 구하는 것이 함수를 실행했을 때 발생하는 총 작업량을 구하는 것과 같아진다는 것이다.

사실 이렇게 정리해놔도 아직 무슨 소리하는지 잘 모르겟다. 

내가 지금 이해할 수 있는것은, 시간복잡도가 함수의 형태로 그려질 수 있고, 이것을 적분함으로써 시간복잡도를 근사해 그릴 수 있다는 아이디어가 사용된다는 것 정도일 것이다. 

이 시간복잡도의 분석과 증명은 학계에서 해줄테니,

우리 개발자 입장에서는 "음 이런 원리로 이 함수를 쓰면 이정도 시간안에 문제를 해결 할 수 있겠구나"를 추측하고 효과적으로 사용할 수 있는 것 정도로 받아들이면 될 것 같다.

다음은 지피티한테 설명해달라고한 에라토스테네스의 체의 시간복잡도이다.