I. 시간복잡도
일반적으로 1억 번(10^8)의 연산은 1초입니다.
빅- 오 O(n) 표기법을 기준으로 코딩테스트에서 수행시간을 계산합니다. 모든 테케를 통과해야만 합격으로 판단하므로 최악일 때를 염두해야 합니다.
- 시간 복잡도 표기법
빅-오메가 : 최선일 때 연산 횟수
빅-세타 : 보통일 때 연산횟수
빅-오 : 최악일 때 연산횟수
- 알고리즘 문제를 풀 때
10^8 = 1억번을 기준으로 빅-오 표기법을 기준으로 문제를 풀어야 합니다.
II. 리스트
(1) 연결 리스트
- 데이터 검색의 경우
선형 리스트의 경우 ArrayList인데, 검색은 O(1) 만큼의 시간 복잡도가 발생합니다
연결리스트의 경우 LinkedList인데, 연결 리스트의 값들을 서로 연결되어 있으므로 O(n)만큼의 시간 복잡도가 발생합니다.
- 데이터 삽입, 삭제의 경우
선형 리스트의 경우 ArrayList인데, 삽입 삭제는 O(n) 만큼의 시간 복잡도가 발생합니다.
→ 이유는 데이터를 삽입하거나 삭제하기 위해서 앞이나 뒤의 데이터들을 이동 시켜야 하기 때문입니다.
연결리스트의 경우 LinkedList인데, 연결 리스트의 값들을 서로 연결되어 있으므로 O(1)만큼의 시간 복잡도가 발생합니다. 모두 연결되어 있으므로 삽입할 때는 새로 그 값만 연결하면 되고 삭제할 때도 마찬가지로 그 값과 연결된 주소들을 변경하기만 하면 되기 때문입니다.
(2) ArrayList vs LinkedList
- ArrayList
배열 기반의 자료 구조이며 사이즈가 가변적입니다. Object 타입 만 넣을 수 있는데 Integer, Boolean 등이 해당됩니다.
ex. ArrayList<Integer> arr = new ArrayList<>();배열과 유사하게 인덱스로 바로 값에 접근할 수 있어서 시간 복잡도가 O(1)이지만, 삽입이나 삭제를 할 경우 데이터들을 모두 이동시켜야 한다는 단점이 있습니다.
- LinkedList
이중 연결 리스트 기반 자료구조이며 사이즈가 가변적입니다.. Object 타입 만 넣을 수 있는데 Integer, Boolean 등이 해당됩니다.
ex. LinkedList<Integer> link_list = new LinkedList<>();⇒ 공통점
연결리스트와 선형 리스트는 사용되는 메서드는 모두 같지만, 안의 내부 구조가 차이가 있어서, 삽입과 삭제시 데이터가 많을수록ArrayList 의 실행시간이 엄청나게 오래걸린다는 점입니다. 마지막 인덱스에 값을 추가하는 경우에는 데이터가 많을수록 LinkedList 의 실행시간이 엄청나게 오래걸린다는 점도 특징입니다.
