Big O of Arrays

😁 배열에서의 Big O

배열의 기능에 따른 속도

• 삽입 : 내용에 따라..
• 제거 : 내용에 따라.. 다르다
• 검색 : O(N)
• 접근 : O(1)

접근이 O(1)인 이유는 배열에서는 인덱스가 있기 때문에 인덱스로 바로 접근이 가능하기 때문에 O(1)이다.
그러나 삽입은 다르다.

삽입과 제거

let fruits = [ "apple", "banana", "pineapple"] 
                0         1         2 

위와 같은 배열이 있다고 하자 만약 배열의 맨 끝에 "orange"를 추가한다면 똑같이 O(1)시간이 든다.
그러나 배열의 앞이나 중간에 입력했을 때가 문제이다.

let fruits = ["orange" "apple", "banana", "pineapple"] 
                          0         1         2 

이렇게 추가됐을 시 인덱스가 엉망이 되고 바로잡기 위해서는 인덱스를 다 옮겨주어야 한다.
위와같이 엘리먼트가 몇개 없다면 오래걸리지 않겠지만 많으면 많을 수록 시간은 많이 걸릴 것이다.
따라서 앞에 추가한다면 O(N)이다. 크기에 따라 시간이 오래걸리기 때문이다.
제거도 마찬가지이다.

🍳 검색

검색의 경우도 마찬가지로 O(N)이다. 왜냐하면 만약 apple을 찾고자 한다면 요소를 처음부터 하나씩 뒤져본다.
즉 엘리먼트가 많아질수록 걸리는 시간이 오래걸리기 때문에 O(N)이다.

🧇 Big O of Array Operations

• push : O(1)

• pop : O(1)

• shift : O(N)

• unshift : O(N)

• concat : O(N)

• slice : O(N)

• splice : O(N)

• sort :O(N*logN)

• forEach/map/filter/reduce/etc - O(N)

🥩 객체와 배열의 차이점

• 객체는 거의 모든 것을 빠르게 하지만 정렬되어 있지 않음
• 배열은 정렬되어 있지만 끝에 추가 및 제거하는 작업이
  시작에 추가,제거하는 것보다 빠르다.