[알고리즘] 배열의 시간복잡도

*강의를 보고 정리한 노트입니다. 

 

배열에 있는 데이터의 접근은 매우매우 빠른데 아래와 같이 각각의 역할에 따라 빅오가 달라진다. 

 

접근  -  O(1) 배열의 접근은 인덱스를 사용하여 매우매우 빠르게 접근이 가능함

입력  -  배열끝에 추가하면 O(1)이지만, 배열 앞에 추가 및 삭제를 하게 되면 배열의 모든 인덱스를 새롭게 배정해주어야 하기 때문에 O(n)

탐색  -  O(n) 배열의 모든 인덱스를 거쳐서 탐색을 해야하기 때문

 

배열 메소드의 빅오

 

push / pop

: O(1)  -  배열의 맨끝에 추가하고 제거하는 작업은 배열의 크기와 상관이 없고 그냥 끝에 넣거나 삭제해주기만 하면 끝!

 

 

shift / unshift

: O(n)  -  배열 시작에 추가하고 제거를 한다면 무조건! 인덱스를 재정의하게 됨

 

 

concat

: O(n)  -  여러개의 배열을 하나의 배열로 합추어줌, 즉 배열의 크기만큼 시간도 늘어나게됨

: [배열명].concat([배열명]);

 

 

slice

: O(n)  -  배열의 일부를 가져오거나 전부를 가져옴

 

 

splice

: O(n)  -  엘레먼트를 제거하고 추가함, 배열 시작에 추가할 수 있고, 배열 끝에도 추가할 수 있음

 

 

sort

: O(n*logn)  -  가장느림!! 배열의 정렬은 한번의 작업만으로 정렬 작업을 완료할수가 없고 아주 복잡하게 진행됨

 

 

forEach / map / fitter / reduce / etc 

: O(n) 

 

 

배열로 할 수 있는 대부분은 O(n)의 시간복잡도를 갖게 됨