시간복잡도-1

안녕하세요. 이제부터 알고리즘에 관한 내용을 올릴 주인장되는 사람입니다

뭐 짜디시리 할 말도 없고 바로 본 내용으로 넘어가도록 하겠습니다.

첫번째로 알아볼 얘기는 시간복잡도(Time Complexity)입니다.

PS 대회에서 채점 요소는 3가지가 있습니다.

첫 번째는 당연하겠지만 각 경우의 답입니다. 답이 맞아야죠

두 번째는 시간입니다. 제한시간내에 답을 내야한다는 것이죠.

세 번째는 공간입니다. 주어진 메모리내에 문제를 해결할 수 있어야 한다는 겁니다.

첫 번째는 너무 당연한 요소기 때문에 중요한 요소에서 제외한다치면, 시간과 공간이 남게 됩니다.

과연 이 둘중에서 대회에서 더 중요하게 보는 것은 무엇일까요? 바로 시간입니다.

공간은 여유롭게 주는 반면에, 시간은 빡빡하게 주는 것을 볼 수 있습니다.

따라서 여러분들이 대회에서 문제를 해결할 때, 대충 내가 짠 코드가 최악의 경우에 얼마의 시간이 걸릴지 예측을 하고 있어야 합니다.

만약 제한시간이 1초인 문제에서 5초가 나온다면 잘못된 소스일 것이니까요

이 예측을 가능하게 해주는 요소를 우리는 시간복잡도라고 합니다.

시간 복잡도에도 종류가 있습니다. 첫번째는 우리가 흔히 사용하는 빅오 계산법이고, 두 번째는 세타 계산법입니다.

저희는 빅오 계산법에 초점을 맞출 예정입니다.

그리고, 절대 간과하면 안되는 것이, 이 시간계산법은 대충 예상하는거지 '정확하게' 예상하는 것이 아닙니다.

예를 들어, 입력의 최대 크기가 n일때, n^2의 시간이 걸린다하면, 정확하게 n^2의 시간이 아니라, 대략 n^2의 시간이 걸린다는 겁니다.

일단 그렇게 알고, 본론으로 들어가죠

첫 번째로 말씀드릴것은, 주먹구구 법칙입니다.

주먹구구 법칙은 일종의 관찰의 법칙입니다.

프로그래머들이 알고리즘이 돌아지는것을 보고 1초엔 대략 몇번 연산할 수 있더라. 라고 정한것이죠.

사실상 돌아가는 것은 CPU에 많이 의존을 하기 때문에, 모든 컴퓨터의 1초 연산량이 같을 수는 없습니다.

또한, 경우에 따라 같은 컴퓨터라도 1초에 처리하는 양은 다를 수가 있습니다.

그러므로 주먹구구 법칙은 항상 성립한다고 할 수 없고, 각 경우에 따라 다를 수도 있습니다.

대회에서 프로그램의 처리시간이 제한시간이랑 아슬아슬하게 차이가 날 경우, 다른 테스트 케이스나 한번 더 테스트 케이스를 넣어보는 경우는 이 때문입니다.

주먹구구 법칙에 의하면, 1초에 대략 컴퓨터가 처리하는 양은 10^9, 즉 1억 번 정도라는 것입니다.

대부분 계산은 이 법칙을 통해서 하고, 이 법칙에 들어맞더라도 초과가 나는 경우가 있습니다.

두 번째로 알아볼 것은, 빅 O계산법입니다.

빅O 계산법의 핵심은 큰 것이 복잡도를 지배한다 입니다.

예를 들어보자면, 수열의 극한 계산할 때, 분수의 극한 계산하실 때를 생각해보세요.

분모와 분자가 다항식일 경우에, 뒤에 어떤 큰 값이 존재하든간에 최고차항의 차수와 계수에 의해 극한값이 정해집니다.

이가 의미하는것은, 뒤에 있는 계수들이 아무리 커져봤자, 극한으로 가는 수가 커지면 결국 많이 곱해지는 것이 제일 커진다는 것입니다.

빅O 계산법도 이를 전제로 하고 갑니다. 예를 들어보죠

만약 계산을 하는데 의 시간이 필요하다고 가정합시다. 원래 걸리는 시간은 저렇지만, 빅 O에서는 2는 치워버리고 만 적습니다.

다른 예시로 의 시간이 걸리는 알고리즘이 있습니다. 과연 이를 빅O 계산법으로 처리하면 어떻게 될까요?

우리는 예전에 배운적이 있습니다. 무한대에 자연수를 곱해봤자 무한대이다. 이 말은, 엄청 큰 것에 작은 정수 하나 곱해봤자, 어짜피 엄청 큰 수일 것이다.라는 것입니다.

따라서, 빅O 계산법에서는 이나 이나 같게 봅니다. 즉, 앞에서 말했던 것을 빅O로 표현하면 이 된다는 것이지요.

이를 통해서 본격적인 계산을 하는 과정은 2부에서 다뤄보도록 하겠습니다.

질문은 댓글 달아주시면 확인하는대로 최대한 빠르게 답변드리겠습니다.

감사합니다.