알고리즘에 대해 공부를 하였다.

알고리즘

알고리즘은 문제가 있을 때, 그 문제를 해결하는데 있어서 길을 제시해 주는 것이다. 네비게이션을 찍었을 때, 최소한으로 걸리는 길을 찍어주는 느낌 이라고 생각하면 된다.

알고리즘은 여러가지가 존재할 수 있는데, 이 중에서 좋은 알고리즘을 판별하는 방법은 점근표기법으로 각 알고리즘의 함수를 비교하는 방법이 있다.

시간복잡도

시간복잡도는 입력값과 문제 해결에 걸리는 시간과의 상관관계이다.
시간이 적게 걸릴수록 좋은 알고리즘이다.
보통 입력값을 N이라고 했을때, 연산량이 얼마나 되는가를 확인한다.
모든 코드를 매 실행단위로 체크하는것은 사실상 불가능에 가깝기 때문에 N에 비례하여 얼마나 커지는지만 보면 된다.
N의 값이 무한대로 커짐에 따라 상수는 N값에 비하면 무시해도 되는 수치가 되므로 N의 지수만 확인하면 된다.
상수가 필요하다면 +1로 생각하면 된다.

공간복잡도

공간복잡도는 입력값과 문제 해결에 필요한 공간과의 상관관계이다.
시간과 마찬가지로 공간도 적게 차지할수록 좋은 알고리즘이다.
다만, 공간복잡도가 작다고 해서 꼭 좋은 알고리즘인건 아니다.
보통 공간복잡도는 상수의 형태를 띄기 때문에 알고리즘의 성능에 전혀 영향을 미치지 못한다.
따라서 공간복잡도를 다소 희생하더라도 시간복잡도가 작은 알고리즘이 더 좋은 알고리즘이라고 말할 수 있다.

알고리즘의 표기법 Big-Ω 와 Big-O

Big-Ω 표기법은 최선의 성능이 나올 때, 어느정도의 연산량인지를 표시한다.
표기 방법은 Ω(1)과 같은 형식이다.

Big-O 표기법은 최악의 성능이 나올 때, 어느정도의 연산량인지를 표시한다.
표기 방법은 O(N)과 같은 형식이다.

이런식으로 최선의 성능과 최악의 성능이 나뉘어 있는 이유는 알고리즘의 성능은 항상 일정하지 않기 때문이다. 입력값과 입력값의 분포에 따라 성능이 달라지게 된다.
예를들면 입력값이 N일 때, 첫번째 계산에 운좋게 끝나는 경우도 있고,
N번째까지 모두 확인한 다음에 끝나는 경우도 있을 것이다.
이 경우에 O(N)Ω(1)의 시간 복잡도를 가진 알고리즘이라 한다.
알고리즘을 표기할 때 거의 대부분 Big-O표기법을 사용한다.
알고리즘이 최선의 결과가 나오는 경우는 거의 없고, 항상 최악의 상황에 대비해야 하기 때문이다.

for문 에서 array의 길이만큼 반복하게 된다면, 그 알고리즘의 시간복잡도는 O(N)이 된다.

알고리즘을 공부하면서 내가 생각한게 항상 최선의 결과가 나오지 않고, 이보다 더 좋은 수가 있다는 것을 알았다. 좋은 알고리즘을 만드는 것은 알고리즘을 차차 개선시켜 나가는 것이다.
또, 알고리즘을 공부하면서 알고리즘 문제를 보고 이 알고리즘을 푸는 방법은 알겠는데 막상 코드로 구현하려니 막히는 느낌이 들었다.
아직은 내 머리속의 생각들이 코드로 구현이 되지 않는다.
응용이 되지 않기 때문일 것이다.
조금 더 알고리즘에 익숙해져서 문제를 마주했을 때, 내 머릿속의 코드들을 실제로 구현하는것이 가능해지고 싶다.