[Swift] 복잡도 / Complexity

알고리즘의 성능을 나타내는 척도.

시간 복잡도와 공간 복잡도로 나눌 수 있다.

- 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양

---

빅오 표기법

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

---

시간 복잡도

데이터의 개수 N이 천만개(10^7)를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것으로 예상할 수 있다.

데이터의 크기나 탐색 범위가 백억이나 천억(10^10 ~10^11)을 넘가는 경우 O(logN)의 시간 복잡도를 갖는 알고리즘을 작성해야한다.

제한시간이 1초인 경우

N의 범위	시간 복잡도
500 (5 * 10^2)	O(N^3)
2000 (2 * 10^3)	O(N^2)
100000 (10^5)	O(NlogN)
10000000 (10^7)	O(N)

알고리즘 문제에 대한 전략을 시간 복잡도와 N의 범위로 산정할 수 있다.

 

공간 복잡도

책에서 소개된 int는 인접 list로 되어있으며 대개는 이정도의 메모리를 차지하게 된다.

- int a[1000] : 4KB
- int a[1000000]: 4MB
- int a[2000][2000]: 16MB

보통 메모리 사용량을 128 ~ 512MB 정도로 제한하는데, 일반적인 경우 데이터의 개수가 천만 단위가 넘지 않도록 알고리즘을 설계해야한다는 의미가 된다. 

Swift에서의 Array는 동적 배열로 구현되어 있으며, 이는 Array가 고정 크기를 가지지 않고, 요소가 추가되거나 제거될 때마다 크기를 조정할 수 있다는 것을 의미한다.

Swift의 Array에 대한 메모리 사용량을 이해하려면 먼저 Swift에서 Int의 크기를 이해해야 합니다. 64비트 시스템에서 Int는 8바이트를 차지하고, 32비트 시스템에서는 4바이트를 차지합니다. 그리고 Array는 요소의 수에 따라 메모리를 차지한다.

예를 들어, 64비트 시스템에서 1000개의 Int 요소를 가진 Array는 대략 8,000바이트 (또는 8KB)의 메모리를 차지한다. 이는 각 Int가 8바이트를 차지하고, 이것이 1000개가 있기 때문, 하지만 이는 근사치이며, 실제 메모리 사용량은 Array의 내부 구조, 메타데이터, 운영 체제, 그리고 메모리 관리 시스템 등 다양한 요인에 따라 달라질 수 있다.

또한, Swift의 Array는 동적 배열이므로, 요소가 추가되거나 제거될 때마다 메모리 할당이 변경될 수 있다. 이 점에 유의해야 한다.

 

시간과 메모리 측정

[Swift] 함수간 걸린시간 측정 / 실행 시간 / 코드 실행 시간 측정

 

 

---