[면접대비] Array, Linked List
복잡도(Complexity)
알고리즘의 성능, 효율성을 나타내는 척도다.
최악의 경우를 가정해서 알고리즘 성능을 파악한다.
- 시간 복잡도(Time Complexity): 알고리즘의 수행 시간에 대한 척도.
- 공간 복잡도(Space Complexity): 알고리즘의 메모리 사용량에 대한 척도.
- 보통 시간 복잡도와 공간 복잡도는 반비례한다.
시간 복잡도 구하기
입력을 기준으로 할 때 필요한 연산 횟수에 따라 결정된다.
시간 복잡도가 너무 크면 주어진 시간이 초과될 수 있다.
공간 복잡도 구하기
고정 공간: 코드가 저장되는 공간 등.
가변 공간: 알고리즘에 따라 달라지는 공간. 변수를 저장하는 공간, 순환 스택 등.
내부에서 생성된 배열 등의 차원에 따라 결정된다.
재귀함수일 경우 스텍이 쌓이면서 공간 복잡도가 높아질 수 있다.
공간 복잡도가 너무 크면 프로그램이 메모리에 올라가지 않아 실행할 수 없다.
빅데이터 처리시 데이터를 나누고 다시 합쳐서 처리할 수 있다.
Array와 시간복잡도
논리적인 저장 순서와 물리적인 저장 순서가 일치한다.
데이터 찾기: 인덱스 값을 알고 있다면 array[index] 형식으로 바로 전달할 수 있다. O(1)
데이터 삽입: 자리를 찾은 후, 삽입하고, 이후의 데이터를 다 밀어야 한다. O(n)
데이터 삭제: 자리를 찾은 후, 삭제하고, 이후의 데이터를 하나씩 앞으로 당겨야 한다. O(n)
Linked List와 시간복잡도
논리적인 저장 순서와 물리적인 저장 순서가 일치하지 않다.
각각의 원소들은 자기 앞에 어떤 원소인지를 기억한다.
데이터 찾기: 가장 앞 노드부터 데이터를 찾는다. 선형 탐색이라고 한다. O(n)
데이터 삽입: 삽입할 노드의 주변 노드들의 Link만 수정한다. O(1)
데이터 삭제: 삭제할 노드의 주벼 노드들의 Link만 수정한다. O(1)
메모리 사용: Array와 Linked List의 차이점
1. 배열은 사용하기 전 배열의 크기를 미리 선언해야 하고, 크기의 수정이 불가능하기 때문에 메모리 사용이 비효율적이다. (정적 할당)
2. 연결 리스트는 필요할 때마다 노드를 생성하여 연결하면 되기 때문에 메모리를 효율적으로 사용할 수 있다. (동적 할당)
3. 배열은 메모리 공간에 연속적으로 저장되어 있는 자료구조이다. 이러한 특징때문에 인덱스를 통한 접근이 용이하고, 데이터 외에 다른 정보를 저장할 필요가 없다.
4. 연결 리스트는 데이터를 저장할 공간 뿐만 아니라, 다음 노드의 주소를 저장하는 공간이 추가적으로 필요하다.