[TIL] 20240325 29일차

프로그램 복잡도

시간, 공간은 반비례 성향을 가진다.

즉, 시간 복잡도가 감소하면 공간 복잡도가 증가하고

시간 복잡도가 증가하면 공간 복잡도가 감소함.

 

그러나 기술이 발전함에 따라 저장 공간은 충분한 크기를 가지게 되었으므로

프로그램 설계에 있어 시간 복잡도가 핵심이 된다.

알고리즘 적용 시 시간 복잡도를 더 중점으로 생각

 

---

공간 복잡도

 

가. 정의: 프로그램을 실행 및 완료하는 데에 필요한 저장 공간의 크기(양)

 

 

나. 저장 공간의 분류

 

1. 고정 공간 (Fixed Static Part)

코드 저장 공간. 단순 변수 및 상수가 저장되는 공간. Cp

 

2. 가변 공간 (Variable Dynamic Part)

프로그램 실행 중 동적으로 필요한 크기가 변화하는 공간. Sp

 

총 필요 공간 S(p)는 고정 공간과 가변 공간의 합으로 표현한다.

S(p) = Cp + Sp

 

★ Cp는 상수로 취급되므로 총 필요 공간은 가변 공간에 좌우된다.

 

 

다. 공간 복잡도의 예시

 

Big-O Notation으로 표기. (최악의 경우의 공간 복잡도 표기)

- O(1): 단순 변수 선언만 된 경우

- O(n): 1차원 배열 선언, 재귀(recursion) 사용 등

- O(n²): 2차원 배열 선언 등

 

 

라. 운영체제, 프로세스, 메모리, 스레드 전체 구조

 

운영체제 아래 프로그램 별로 프로세스를 실행하고 각 프로세스에 맞는 메모리를 할당받는다.

 

1. 프로세스

- 컴퓨터에서 연속적으로 실행하고 있는 컴퓨터 프로그램
- 메모리에 올라와 실행되고 있는 프로그램의 인스턴스 (독립적인 개체)
- 운영체제로부터 시스템 자원을 할당받는 자원의 단위

 

프로세스 별 할당받은 메모리에는 4개 영역으로 나뉘며, 각 영역은 코드 영역, 데이터 영역, 힙 영역, 스택 영역이다.

(마. 항목에서 자세히 다룸)

 

스택 영역에서 각 스레드 별로 독립적인 스택 영역을 할당 받는다.

각 스레드 들은 코드, 데이터, 힙 영역 간 데이터 교환이 가능하다. 따라서 스레드 간 데이터 교환이 가능하다.

 

프로세스 간 데이터 통신이 불가능한 것은 아니나, 별도 방법을 마련해야 한다.

이들을 총칭하여 IPC(Inter Process Communication) 라고 한다.

 

 

마. 메모리에서 각 영역과 역할

 

---

 

시간 복잡도