서론
알고리즘을 만들 때 다들 고민을 한 번쯤은 해봤을 것이다. 여기서 Array를 쓰는게 더 효율적인지 Object를 사용하는 것이 더 효율적인지. Big O 개념을 알았다면 이제 둘 중 어떤것이 더 효율적인지 표기할 수 있다!
지금까지 배운 BigO개념을 이용해서 Array와 Object가 어떻게 동작하고 성능이 어떻게 차이가 나는지 알아보겠다.
본론
Array에서의 Big O
//javascript에서의 Array 선언 방법
const people = ["jhon", "johnny"];javascript에서 다음과 같은 방식으로 Array를 선언한다. 선언한 Array안에 element에는 0부터 차례대로 인덱스가 순서대로 부여되어있으며, 그 순서대로 배열이 정렬되어있다.
배열은 정렬된 데이터를 이용할 때에는 편리하지만, 그렇지 않은 데이터를 사용할 때에는 비효율적인 편이다.
배열의 맨 끝에 데이터를 삽입하거나 삭제할 때에는 O(1)로 빠르게 처리할 수 있다. 하지만 배열의 앞이나 중간에 데이터를 삽입, 삭제할 때에는 O(n)의 시간복잡도가 된다.
왜 이런 것일까? 그 이유는 배열은 인덱스로 정렬되어있기 때문이다. 만약 내가 맨 앞에 데이터를 추가하거나 삭제해서 변경시킨다면 뒤에 데이터들에 부여된 인덱스들을 모두 재정렬할 필요가 생긴다. 그 때문에 O(n)의 시간복잡도가 생긴다. 맨 끝에 데이터를 삽입하거나 삭제할 때에는 배열을 다시 정렬할 필요가 없기 때문에 문제가 없다.
배열에서 search할때의 시간복잡도도 O(n)이다. 하지만 만약 인덱스를 가지고 접근을 한다면 O(1)의 상수복잡도가 된다.
메서드에서도 마찬가지이다. 배열에서의 pop과 push는 O(1)이고 shift와 unshift는 O(n)이다.
재정렬이 필요한 메서드들은 대부분 O(n)이지만, sort에서는 O(n*logn)로 더욱 더 느리다.
Object에서의 Big O
//javascript에서의 Object 선언 방법
const people = {
eye : "brown",
hair : "black",
language : "Korea",
age : 26
}javascript에서는 다음과 같이 key와 value매칭하여 Object를 선언한다.
Object는 Array처럼 정리되어 있지는 않지만, 정렬되어있지 않기 때문에 삽입과 삭제를 할 때 모든 요소를 재정렬할 필요가 없어 상수복잡도 O(1)로 빠르게 처리할 수 있다.
key를 이용해서 접근할 때에도 마찬가지이다 O(1)로 빠르게 처리할 수 있다.
다만 element를 이용해서 search할 때에는 모든 요소를 확인해야하기 때문에 O(n)의 시간복잡도를 가진다.
메서드에서는 Object.keys, Object.values와 같이 배열로 리턴하는 메서드들은 element가 늘어날 수록 배열에 추가하는 연산의 갯수가 늘어나기 때문에 O(n)의 시간복잡도를 가지고, hasOwnProperty는 key값을 가지고 접근해 속성이 있는지만 전달하기 때문에 O(1)의 시간복잡도를 가진다.
결론
결론적으로 Object와 비교하면 배열은 많이 비효율적이다. 물론 때에 따라 배열이 더 효율적으로 사용되겠지만, 일반적으로 객체를 사용하는 것이 더 효율적인 알고리즘을 만들 수 있다. 이번 Big O개념을 공부하면서 코드의 효율에 대해 더 생각하게 되었고, 제일 충격을 받은건 코드의 길이를 줄이려고 사용한 sort메서드가 이렇게나 많은 시간이 소요된다는 것이었다. 짧은 코드 보다 시간과 메모리 효율이 더 중요하다. sort를 사용하는건 ... 자제해야겠다.
참고
