알고리즘 복잡도

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

2. 빅오
시간 복잡도를 표현할 때 빅오(BIG-O) 표기법 사용. 
빅오 표기법은 가장 빠르게 증가하는 항(큰 차수를 가진 항)만 고려하는 표기법이다.

 

아래는 빅오 표기법 종류에 대해 설명하는 사진이다.

출처: 이것이 코딩테스트다/ 나동빈 책

 

O(1) = 상수 연산. 연산 한 번이 수행된다.
ex) a=5 b=7 print(a+b)

O(n^2) = 보통 2중 반복문(for) 이용.  그러나 모든 2중 반복문 시간 복잡도가 O(n^2)이 아니다. 만약 코드가 내부적으로 다른 함수를 호출하면 내부 함수의 시간 복잡도까지 고려해야 한다.


3. 알고리즘 설계 Tip
컴퓨터 연산 횟수가 5억 넘을 경우:C언어를 기준으로 1초 이상 시간 소요.
O(N^3)의 알고리즘을 설계한 경우, N의 값이 5000이 넘는다면? 1000억... 
코딩 테스트 문제에서 시간제한은 1~5초 걸린다. 따라서 O(N^3) 설계는 삼가해야한다.