복잡도

👣 시간 복잡도

👣 Big - O 표기법

Big-O 표기법은 알고리즘의 시간 복잡도를 표현하는 방법 중 하나로,
알고리즘이 얼마나 빨리 실행되는지를 나타내는 지표.

다른 평가지표에 비해 Big-O 표기법은 매우 비관적으로 시간 복잡도를 평가한다.
때문에 최악의 경우의 알고리즘의 성능을 표기.

알고리즘의 시간 복잡도는 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타내며,
이를 통해 알고리즘의 효율성을 평가할 수 있음.

👣 복잡도가 최고 차항의 단항식에만 집중하는 이유 - 개인적인 의견

1. Big-O 표기법이라는 것 자체가 최악의 시나리오에서의 알고리즘 성능을 측정하는 것.
최악의 상황은 입력 데이터 갯수가 커질 때 발생하기 마련이다.

2. 사실 입력 데이터의 갯수(n)가 적다면 알고리즘 사이의 차이가 기껏해봐야 100ms 차이 내외일 것이다.
알고리즘의 의미가 생기려면 n의 크기가 커야 한다.
고등학교에서의 수렴 개념을 고려한다면 결국 큰 수에서의 게임 체인저는 최고 차항의 단항식일 것이다.

3. '시간 복잡도가 곧 시간을 측정해준다'라는 생각은 부정확할 수 밖에 없다.
해당 알고리즘을 돌리는 프로세서의 성능, 내부 상황 등등의 이유로 작동 시간은 정확하게 예측할 수 없다.
다만, 알고리즘 사이에는 분명 훨씬 좋은 성능을 가진 알고리즘이 존재할 것이고
그러한 우위를 비교하는 지표들 중 하나인 Big-O 표기법을 사용하는 것일 뿐이다.

👣 공간 복잡도

프로그램을 실행했을 때, 필요로하는 자원 공간의 양.

int a[1000];

위와 같은 코드가 있을 때, 변수 a는 4000 Byte의 메모리 공간을 요구한다.
이와 같은 부분을 일컫는다.