알고리즘이란?
알고리즘은 잘 정의된 문제 해결들의 모음집 입니다. 주어진 문제들을 해결하기 위한 방법들을 제공합니다.
알고리즘의 특징
알고리즘 측정
어떤 문제를 해결하는데 다양한 해결방법이 존재합니다. 하지만 그런 해결방법들이 항상 좋은 방법은 아닙니다.
알고리즘의 성능측정은 이런 비교를 위해 필요합니다.
하지만 알고리즘의 절대적인 측정은 쉽지않습니다. 왜냐하면 다양한 환경에서 같은 알고리즘을 실행할 경우 다른 성능을 보여주기 때문입니다.
알고리즘의 성능을 측정하는 기준은 대표적으로 시간복잡도(Time complexity) 와 공간복잡도(Space complexity) 를 측정합니다.
시간복잡도는 알고리즘을 사용해서 문제를 해결하는데 걸리는 시간을 의미하며, 공간복잡도는 알고리즘을 해결하는데 사용되는 메모리를 말합니다.
알고리즘의 성능표기법
알고리즘의 성능 표기법으론 대표적으로 다음 방법들이 사용됩니다.
Big-O 표기법
빅오표기법은 수학적 표기법을 사용해서 복잡도를 표현합니다.
빅오표기법은 다음의 두가지 특징이 있습니다.
위의 코드는 입력되는 n의 크기에 따라 n + 2 만큼의 로직이 수행됩니다.
그런데 n이 커지면 커질수록 n+2 와 n의 차이가 의미가 없습니다.
그래서 빅오표기법에선 O(n) 으로 표기됩니다.
객체와 배열의 Big-O
객체는 key-value 의 한 쌍으로 이루어진 값들의 집합입니다.
객체의 각 상황에 대해 Big-O 표기법으로 표현해보겠습니다.
Object의 각 값을 수정할 땐 key를 통해 접근이 가능하기 때문에 O(1) 의 복잡도를 가집니다.
하지만 각 요소들에 대해 작업을 수행해야 한다면 O(n)만큼의 작업이 수행됩니다.
배열은 일렬로 나열된 값들의 집합입니다.
배열의 각 상황에 대해 표시해보겠습니다.
일반적으로 배열의 map/filter/reduce는 많이 사용됩니다. 그래서 이런 복잡도에 대해 이해하고 있으면, 코드작성할 때 성능을 생각하며 작성할 수 있을것입니다.
