#1. 시간복잡도와 공간복잡도

시간 복잡도

알고리즘이 입력 크기에 따라 실행에 필요한 시간을 측정한다.

알고리즘이 입력 크기가 커질수록 얼마나 느려지는지 예측되는지 도움이 되며, 일반적으로 시간 복잡도는 입력 크기의 함수로 표현된다. 

알고리즘의 시간 복잡도를 나타내는 표기법은 Big-O 표기법 이다.

시간 복잡도가 O(1)인 경우 알고리즘이 실행되는 동안 입력의 크기에 상관없이 일정한 시간만큼 걸린다는 것을 의미한다.

즉, 입력의 크기가 증가하더라도 알고리즘의 시간은 일정하다는 것이다. 

또한 O(n) 에서 n 이 1에 가까울 수록 알고리즘의 실행시간이 짧아진다. 

 

1. 상수 시간 복잡도(Constant time complexity)
   
   • 알고리즘의 실행 시간이 입력 크기와 무관하게 일정한 상수 시간이 걸리는 경우
   • 예를 들어 배열에서 인덱스를 찾는 A[i]는 상수 시간 복잡도 O(1)를 갖는다.
   • 배열의 크기와 상관없이 인덱스를 찾는 데에는 일정한 실행 시간이 걸린다.
2. 선형 시간 복잡도(Linear time complexity)
   • 알고리즘의 실행 시간이 입력 크기에 비례해 증가하는 경우
   • 예를 들어 배열의 모든 요소를 출력하는 연산은 배열의 크기에 비례해 실행시간이 증가한다. 
3. 이차 시간 복잡도(Quadratic time complexity)
   • 알고리즘의 실행 시간이 입력 크기의 제곱에 비례하는 경우
   • 예를 들어, 이중 반복문을 사용해 배열의 모든 요소 쌍을 출력하는 연산은 이차 시간 복잡도 O(n^2)를 갖는다.
4. 로그 시간 복잡도(Logarithmic time complexity)
   •  알고리즘의 실행 시간이 입력 크기의 로그에 비례해 증가하는 경우
   • 일반적으로 데이터를 이진 검색하는 경우와 같이, 입력 데이터를 반씩 나누어 탐색할 때 발생
   • 로그 시간 복잡도 O(log n)을 갖는다.

 

공간복잡도

알고리즘이 실행되는 데 필요한 메모리 양을 측정한다. 

알고리즘이 메모리를 얼마나 많이 사용하는지를 예측하는 데 도움이 되며, 마찬가지로 입력 크기의 함수로 표현된다. 

입력 크기 함수
- n : 입력 데이터의 개수(정렬 알고리즘의 입력 크기는 정렬할 데이터의 개수를 나타내는 n 이다.)
- m : 입력 데이터의 크기(이미지 처리 알고리즘의 입력 크기는 이미지의 해상도와 크기를 나타내는 m)
- l : 입력 데이터의 길이(문자열 검색 알고리즘의 입력 크기는 검색할 문자열의 길이를 나타내는 i)
- s : 입력 데이터의 크기와 상관없이 고정된 값(알고리즘이 실행되는 데 필요한 메모리 공간과 같은 고정 값은 s)

 

공간 복잡도의 단위 
- 바이트(Byte) 메모리 공간의 크기를 측정하는 가장 작은 단위, 바이트는 일반적으로 알고리즘에서 사용되는 변수 및 데이터 구조의 크기를 사용하는 데 사용된다.

- 킬로바이트(KB) 1,024바이트를 의미한다. 대부분의 컴퓨터가 KB 단위로 측정된다.

- 메가바이트(MB) 1,048,576바이트로 대용량 데이터를 처리할 때 사용된다. 

- 기가바이트(GB) 1,073,741,824바이트로 대용량 처리 및 저장장치 용량 등을 측정할 때 사용