배열의 시간 복잡도

배열 (Array) 같은 타입의 변수들로 이루어진 집합. 배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)이다. 배열의 인덱스는 0부터 시작해 0, 1, 2, 3, ..., size - 1 의 인덱스를 참조할 수 있다. 배열 A의 n번 째에 해당하는 변수는 A[n]으로 표시한다. 배열 내 연산은 크게 접근(access), 검색(search), 추가(add), 제거(remove) 으로 나뉜다. 아래는 크기가 10인 Integer형 배열이며, 1. 접근 접근은 배열 내에서 n번째 인덱스에 해당하는 값을 찾아내는 연산이다. 배열의 접근은 O(1)의 시간복잡도를 갖는다. 따라서 찾고자 하는 값이 몇 번째 인덱스에 있는지 알고 있다면 굉장히 빠..

알고리즘, 자료구조/자료구조 2021.01.29 moonsu