객체의 빅오
객체의 장점은
- 정렬되어 있을 필요가 없을 때 잘 동작한다.
- 빠른 접근, 입력과 제거를 할 때 좋다. 빠르다는 것은 소요되는 시간이 상수 시간으로 O(1)인 것이다. (정렬될, 순회할 필요가 없기 때문에)
- Insertion : O(1)
- Removal : O(1)
- Searching : O(n)
- Access : O(1)
객체의 단점은
탐색에는 선형시간 즉, O(n)이 소요된다. 여기서 탐색이라는 것은 key를 찾는 것이 아니라 key에 저장된 value를 찾는 것이다. 따라서, 원하는 값을 찾기 위해 모든 key를 탐색해야 하는 것이다.
배열 안의 데이터 탐색이 느린 이유
배열은
- 대부분 정렬되어 있는 데이터를 위해 사용한다.
- 접근은 인덱스를 사용하기 때문에 빠르지만 입력과 제거는 느린편이다.
- Insertion : It depends..
- Removal : It depends..
- Searching: O(n)
- Access : O(1)
만약 100개의 요소를 갖는 배열에서 90번 째 요소에 접근하려고 할 때 앞에서부터 모든 요소들을 지나가면서 해당 번째 요소에 도달했을 때 결과를 주는게 아니다. 그렇기에 배열의 길이가 얼마나 긴지는 중요하지 않다.
입력과 제거는 O(n) 시간이 걸린다고 했는데 어디에 입력하고 어디를 제거하는지에 따라 다르다.
입력과 제거를 뒷부분에서 작업하면 상수 시간이 걸리지만 앞부분에서 작업하면 선형 시간이 소요된다. 그 이유는 인덱스 번호에 문제가 발생해 다시 요소 하나하나마다 배정을 해줘야하기 때문이다.
