728x90
시간 복잡도란?
반복문을 몇 번 사용했는지 등을 통해 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수.
즉, 우리는 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.
배열과 링크드 리스트의 차이를 설명해주세요.
LinkedList와 ArrayList는 모두 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체.
- ArrayList
- 내부적으로 데이터를 배열로 관리하고 데이터 추가/삭제 시 임시 배열을 생성해 데이터를 복사함
- 데이터별 인덱스가 있어 검색에는 유리O(1)
- 임시 배열을 사용하기 때문에 데이터 추가/삭제의 경우에는 불리O(n)
- LinkedList
- 내부적으로 노드 단위로 데이터를 관리합니다. 자신의 앞 뒤 노드만 인지하는 상태임.
- 인덱스가 따로 없기 때문에 검색 시 전 노드를 순회해야하여 검색시 불리O(n)
- 데이터 추가O(1)/삭제O(n) 시 불필요한 데이터 복사가 없어 유리
Hash Function, HashTable에 대해서 설명해주세요.
Hash란?
검색과 저장을 아주 빠르게 하기 위해 만든 자료구조
데이터를 저장할 때 key : value 형태로 데이터가 존재함.
key 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어남!
Hash Function이란?
key 값을 고정된 길이의 hash로 변환하는 역할을 함!
이 변환하는 과정을 hashing이라고 함.
hashing을 통해서 해시 값 또는 해시 코드로 변환함!
Hash Table이란?
연관 배열구조를 이용해서 데이터를 key와 value로 저장하는 자료구조이다.
해시 테이블은 해시함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.
장점
- 중복을 제거할 수 있다.
- 데이터 캐싱, 보안에 주로 사용된다.
- 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠르다.
단점
- 공간 복잡도가 커진다.
- 충돌이 발생할 수 있다.
- 충돌이 발생할 경우 시간 복잡도는 O(n)에 가까워진다.
- 순서가 있는 배열에는 어울리지 않는다.
728x90