[모의 면접] 시간 복잡도와 공간 복잡도, 배열과 링크드 리스트

시간 복잡도와 공간 복잡도

복잡도란?
알고리즘의 성능과 효율성을 나타내는 척도로 시간 복잡도와 공간 복잡도로 나뉜다
알고리즘이 주어진 크기의 입력을 기준으로 수행시간과 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다
복잡도를 나타내는 방법은 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용된다.

정리하면 복잡도란 알고리즘의 효율성을 판단하는 척도이다

 

시간 복잡도

연산에 걸리는 시간이 아닌 연산의 횟수를 나타낸다

왜 시간이 아닌 횟수를 측정하는가? 환경에 따라 결과가 다르게 나오기 때문

단순히 특정 입력에 대해 실행되는 연산의 횟수만 보는 게 아닌, 입력의 크기가 증가함에 따라 실행되는 연산의 횟수가 얼마나 증가하는지를 나타낸 것.

시간복잡도를 표기하는 방법 중  가장 많이 사용하는 표기법은  Big-O(빅 오)표기법이다

 

 

• O(1): 상수 시간 복잡도. 입력 크기에 관계없이 실행 시간이 일정하다 (배열의 인덱스를 통한 접근)
• O(n): 선형 시간 복잡도. 입력 크기에 비례해 실행 시간이 증가한다 (리스트를 순회하는 경우)
• O(n^2): 이차 시간 복잡도. 입력 크기의 제곱에 비례해 실행 시간이 증가한다 (이중 루프를 사용하는 경우)
• O(\log n): 로그 시간 복잡도. 입력 크기가 증가할 때 실행 시간이 느리게 증가한다 (이진 탐색)
• O(n \log n): 로그 선형 시간 복잡도. 효율적인 정렬 알고리즘 (병합 정렬, 퀵 정렬).

 

공간 복잡도

프로그램 실행 ~ 완료에 필요한 메모리 공간

알고리즘을 실행시키기 위해 필요한 공간은 두 가지이다

 

알고리즘과 무관한, 고정 공간

코드가 저장되는 공간으로 알고리즘 실행을 위해 시스템이 필요로 하는 공간이다

• 코드 공간 : 프로그램의 코드가 저장되는 공간으로 알고리즘의 입력 크기와 상관없이 일정하다
• 상수 공간 : 알고리즘 실행에 필요한 상수와 기본 데이터타입이 저장되는 공간

 

알고리즘과 밀접한 공간, 가변 공간

문제해결을 위해 알고리즘이 필요로 하는 공간으로 알고리즘 입력 크기, 처리 데이터에 따라 달라진다 알고리즘 실행 과정에서 동적으로 할당되는 공간이다

 

• 변수공간 : 알고리즘 실행 중 생성되는 변수와 데이터 구조(배열)에 필요한 공간으로 입력 데이터 크기나 알고리즘 복잡성에 따라 달라질 수 있다
• 스택 공간 : 재귀호출이나 함수 호출 시 사용하는 스택 메모리, 재귀호출을 사용하는 경우 각 호출에 대해 스택에 추가적인 공간이 필요하다
• 힙 공간 :  동적으로 할당되는 메모리 공간으로 동적 배열이나 객체 생성 시 사용된다 힙 메모리는 알고리즘 데이터와 동적 할당에 따라 변동된다 

 

정리!

시간복잡도는 알고리즘에 걸리는 횟수를 측정하고, 공간복잡도는 알고리즘 실행 시 필요한 메모리 공간이며 동적으로 할당된다 

그리고... 이 이상은 정리가 잘 되지 않는 것 같다. 다시 자료를 찾아보고 정리하도록 하자

---

배열과 링크드 리스트 차이

 

배열

• 정적 자료구조로 정해진 크기에 맞춰 연속된 메모리 주소를 할당받게 된다
• 인덱스(index)를 통해 접근과 탐색에 용이하다
• 정해진 크기 이상의 데이터를 저장할 수 없다는 단점이 있다

 

연결 리스트(Linked List)

• 동적 자료구조로 크기를 정할 필요 없고 배열처럼 연속된 메모리 주소를 할당받지 않는다
• index 대신 Node라는 게 있으며 노드 안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있다 그래서 연결 리스트리고 하는 것
• 크기의 제한이 없기 때문에 추가, 삭제가 자유롭다 하지만 배열처럼 연속적인 메모리 주소를 할당받지 않았기 때문에 임의로 접근하는 것이 불가능하다 왜? 배열은 메모리 주소에 바로 접근 가능하지만 링크드 리스트는 데이터 안에 다음데이터 주소가 있는 식이기 때문 그래서 무조건 순차적인 접근만 가능하다

 

	배열	링크드 리스트
데이터 타입	정적 자료구조	동적 자료구조
크기	정해진 크기가 있음	정해진 크기가 없음
메모리 주소 할당	연속된 메모리 주소를 할당받음	데이터 안에 다음 데이터를 가리키는 주소를 가지고있음 메모리에서 연속적으로 배치되지 않음.
장점	인덱스를 사용해 접근, 탐색에 용이	추가, 삭제에 용이
단점	정해진 크기를 벗어날 수 없음 중간에 요소를 삽입하거나 삭제할 시 배열의 나머지 요소를 이동해야 함.	임의 접근이 어려움 특정 위치의 요소에 접근하려면 처음부터 순차적으로 탐색해야 함
특성	index존재	node 존재