[개인 공부] 기초 알고리즘 2, 소인수 분해의 수행시간, 시간복잡도(추가)

안녕하세요, HoonIOS입니다.

저번에는 알고리즘의 시간 복잡도, 선형 시간 알고리즘, 선형 시간 이하 알고리즘, 이진 탐색인 기초 알고리즘을 알아봤는데요.

 

이곳을 클릭 하시면 저번에 포스팅했던걸 보실 수 있을 겁니다.

 

이번에는 저번 기초 알고리즘에 이은 다항 시간 알고리즘, 지수 시간 알고리즘, 소인수 분해의 수행 시간, 그다음 시간 복잡도에 좀 더 알아보도록 하겠습니다.

 

다항 시간 알고리즘이란?

- 다항 시간 알고리즘이란 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘이다.

예를 들어) n², n...을 말한다.

- 다항 시간은 하나의 분류에 포함되는 알고리즘 간에도 큰 시간 차이가 날 수 있는데 이것은 loop안에도 코드에 따라 큰 시간 차이가 날 수도 있습니다, 그만큼 같은 반복문 이어도 간단한 거와 복잡한 코드가 시간 차이가 난다는 걸 알 수 있겠죠?

- 따라서 알고리즘이 다항 시간이라고 말하는 것만으로 알고리즘이 충분히 빠르다고 할 수 없습니다.

- 이렇게 시간 복잡도에서 차이가 안 좋지만 이들을 묶어서 다항 시간 알고리즘이라고 이름을 붙인 이유는 다항 시간 알고리즘보다 오래 걸리는 알고리즘들이 있기 때문이다.

- 여러 개의 답이 있고 그중 가장 좋은 답을 찾는 문제를 풀 때 가장 간단한 방법은 모든 답을 일일이 고려하는 재귀 함수를 사용하는 건데 이 함수가 다항 시간 알고리즘에 해당한다. 

다항 지수간에 시간복잡도 그래프

지수 시간 알고리즘이란?

- 예를 들어 설명해 보겠습니다, m가지 음식을 만든다 만들지 않는다는 경우의 수를 정할 때 이것의 정답은 2^m  이 되는데 이것을 지수 시간 알고리즘이라고 합니다.

- 따라서 위 예시와 같이 m이 하나 증가 할 때 시간이 배로 증가하는 알고리즘들은 지수 시간에 동작한다고 말하는데 지수 시간은 가장 큰 수행 시간 중 하나로, 입력 크기에 따라 다항 시간과는 비교도 안되게 빠르게 증가한다는 단점이 있습니다.

- 그러나 이 지수 시간 알고리즘도 마찬가지로 현재도 시간 복잡도를 효율적으로 해결하는 방법을 찾아내지 못해 지수 시간 알고리즘들이 많다고 한다.

 소인수 분해의 수행 시간

- 자연수 N이 주어질 때 N이 소인수 분해 결과를 반환하는 간단한 알고리즘을 보여준다.

- 소인수 분해 알고리즘이란 N이 1이 될 때까지 가능한 모든 숫자로 N을 나눠준다. 따라서 N의 크기에 따라 반복문의 수행 횟수가 달라지게 됩니다.

- 소인수 분해 문제에서는 입력으로 주어지는 숫자가 알고리즘의 동작에 직접적인 영향을 미치므로 해당 숫자가 특정 범위 안에 있다고 가정할 수 없습니다.

- N이 아무리 커져도 실제 입력하는 개수는 한 개뿐인데, 수행 시간이 달라지는것은 위에 설명한것과 맞지 않는 이런 불일치가 존재한다.

- 입력의 값이 커지면 이때 입력이 차지하는 비트의 수에 따라 수행시간이 증가한다고 생각 하면 불일치를 직관적으로 설명할 수 있다.

- 즉, 비트의 수 하나가 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간은 두배가 증가한다고 합니다.

시간 복잡도

- 앞에서 설명은 한 적이 있지만 다루지 않은 부분을 좀 더 다뤄보겠습니다.

- 시간 복잡도를 계산할 때 알고리즘을 실행하는 동안 수행하는 기본적은 연산의 수를 통해 표현합니다.

- 기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산이라고 생각하면 된다.

- 즉 쉽게 말하면 가장 깊이 중첩된 반복문의 내부에 있는 기본적 연산들은 더 쪼갤수 없기 때문에, 이것이 시간 복잡도의 기본적인 연산이 됩니다.

- 시간 복잡도가 높다는 말은 입력의 크기가 증가할때 알고리즘의 수행시간이 더 빠르게 증가한다는것을 말합니다.

즉, 시간복잡도가 낮은 알고리즘은 입력이 커지면 커질수록 더 효율적인 알고리즘이 된다는 것입니다.

입력의 종류에 따른 수행 시간의 변화

- 입력의 크기가 수행 시간을 결정하는 유일한 척도는 아닙니다.

- 입력이 어떤 형태로 되어있는지에 따라서 수행 시간에 영향을 미칩니다.

- 예를 들어서 설명하면, 배열에서 특정 문자를 찾을 때 앞에서 발견되거나 중간 혹은 뒤에서 발견되거나 아니면 아예 발견이 안될 수도 있습니다.

- 이렇게 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해서 최선/ 최악의 경우, 평균의 경우에 대한 수행 시간을 따로 계산을 합니다.

- 대게 이 세 개 중에 최악의 수행 시간을 많이 이용하는데 그냥 알고만 있으면 좋을 거 같습니다 :)

 

 

지금까지 기본적인 알고리즘에 대해 좀 더 알아봤고 시간 복잡도 추가된 내용을 알아봤습니다.

 

다음 시간에는 점근적 시간 표기인 O표기와 주먹구구 법칙에 대해 알아보겠습니다 :)

 

좋은 하루 보내시길 빌겠습니다! 오늘 하루도 화이팅 하세요 :)