빅 오(Big O) - 시간복잡도

📗 빅 오(Big O) - 시간복잡도

🔵 시간 복잡도란?

쉽게 말해 알고리즘의 실행속도 계산이다. - 최악의 실행 시간을 계산

알고리즘을 해결하다 보면 시간에 대해서 신경이 쓰일 것이다.

다를 사람의 풀이와 비교한다던지, 시간초과가 발생한다던지... 

 

알고리즘을 해결하는 방법은 다양하다. 그러므로 어떤 알고리즘이 더 효율적인지 분석하기 위해 시간 복잡도를 계산해야 한다.

 

복잡도에는

• 시간 복잡도 - 알고리즘 실행 속도 
• 공간 복잡도 - 메모리 크기(사용량)

이 있지만 보통은 시간 복잡도를 본다.

 

 

🔵 빅오 표기법

• 입력 n에 따라 결정되는 시간 복잡도 함수
• O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n) 등이 있다.
• 상수 O(1): 데이터 수에 상관없이 연산횟수 고정
• 로그 O(logn): 데이터 수 증가율에 비해 연산횟수 증가율이 낮음
• 선형 O(n): 데이터 수와 연산횟수가 비례
• 선형로그 O(nlogn): 데이터 수에 두배 조금 넘게 연산횟수 비례
• 제곱 O(n^2): 주로 반복문이 중첩될 때 발생
• 입력의 크기(n)이 작을 때는 크게 상관이 없지만 n이 커짐에 따라 기하급수적으로 시간 복잡도가 커진다.

 

🔵 빅오 법칙 계산

• 계수 법칙: 입력 크기가 클 때 계수 무시 가능 O(2n) = O(n), O(n + 2) = O(n)
• 합 법칙: 더할 수 있다. O(n) + O(5n) = O(6n)
• 곱 법칙: 곱할 수 있다. O(n) * O(5n) = O(5n^2)

영향력이 없는 항은 무시가능, 가장 큰 지수만을 표기, 최악의 시나리오 가정

ex) O(n^2 + 10n + 10) => O(n^2)