자바스크립트 알고리즘 문제를 100문제 가까이 풀었지만 정작 알고리즘 자체에 대해서는 그냥 코딩으로 문제를 푸는 방법이겠거니 하며 풀었다. 알고리즘과 알고리즘의 시간복잡도에 대해 이론적으로 알아보는 시간을 가져보자.
알고리즘이란
입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열
정확하고 효율적인 알고리즘
알고리즘의 평가할 때는 정확성도 중요하지만, 효율성도 중요합니다.
효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것입니다.
-
예를 들어, 전화번호부에서 Mike Smith를 찾는 일을 한다고 합시다.
전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾습니다.
없으면 그 다음 페이지에서 찾습니다.
Mike Smith 를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복합니다. -
이번에는 더 직관적이고 효율적인 알고리즘을 적용하여 Mike Smith를 찾아봅시다.
먼저, 전화번호부 가운데를 폅니다. 만약 Mike Smith가 그 페이지에 있다면 우리 알고리즘은 끝납니다.
없다면, 전화번호부가 이름순으로 정렬되어 있으므로 우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알고 있습니다.
그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행합니다.
한 페이지가 남을 때까지 계속 수행합니다.
우리는 Mike Smith를 전화번호부에서 찾기 위해 어떤 명령들이 수행되어야 하는지에 대해 두 가지 알고리즘을 찾아봤습니다.
첫 번째 알고리즘은 한 장을 넘긴 다음 또 한 장 넘기는 규칙들의 순서적 나열이었고,
두 번째 알고리즘은 반을 줄이고, 다음 또 반을 줄이는 규칙들의 순서적 나열이었습니다.
두번째 알고리즘은 기존 알고리즘보다 더 효율적입니다.
만약 기존 전화번호부가 100페이지고, 100페이지가 또 추가되어 200페이지가 되었다고 생각해봅시다.
한장 한장 넘기는 첫 번째 알고리즘은 100번의 페이지를 더 넘겨야 하지만, 절반씩 줄어드는 두 번째 알고리즘은 단 1번의 절차만 더 수행하면 됩니다.
단 한 번의 동작으로 200페이지의 반인 100페이지가 사라지기 때문입니다.
알고리즘의 시간복잡도
시간복잡도
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
앞서 이야기했던 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기입니다.
위의 두 가지 경우에서 첫번째 알고리즘은 페이지가 늘어나는 만큼 같은 비율으로 해결하는 시간이 증가합니다. 👉 시간복잡도 N
하지만, 두번째 알고리즘은 100페이지가 늘어나더라도 한 번의 절차만 더 수행하면 되므로 늘어난 문제에 비해 해결시간은 거의 미미하게 증가합니다. 👉 시간복잡도 log n
