시간복잡도(TimeComplexity)

🔆시간복잡도란?

문제를 해결하기 위해 필요한 연산 횟수

1초를 약 1억번의 연산 횟수로 간주한다.
->3초의 제한 시간이 있을 때, 3억번의 연산 횟수 이내로 알고리즘을 작성해야한다.

🔆시간복잡도의 유형

1. Big-Ω: 가장 좋은 상황
2. Big-θ: 평균의 상황
3. Big-O: 최악의 상황
   이 존재하며, 최악인 상황인 빅-오를 기준으로 코드를 짜도록 한다.

🔆Big-O 표기법

O(1) #상수형태
O(logn) #밑이 2인 로그이다.
O(n)
O(n^2)
O(n!)
등으로 표기하며,
상수 형태가 가장 간단하며, 팩토리얼 형태가 가장 복잡하다.

🔆연산 횟수 계산 방법

연산횟수 = 알고리즘 시간 복잡도*데이터의 크기

따라서 연산횟수를 통해 알고리즘이 문제에 적합한지 미리 생각이 가능하다.
ex)100번의 데이터 N이 존재할 때,
버블정렬은 100^2번의 연산 횟수가, 병합정렬은 100log100의 연산 횟수가 필요하다.
따라서, 상황에 맞는 알고리즘을 사용해야 한다.