[알고리즘] 시간복잡도, 공간복잡도 알아보기

알고리즘

달리아(Dahlia) 2022. 11. 26. 02:11

- 보통 1초에 3~5억의 연산을 수행 (연산의 종류마다 달라질 수도 있기 때문에 대략적으로 설명)

- logN 같은 경우 밑의 지수가 보통 2인 경우이기 때문에 log2 = 1, log4 = 2, ... , log64 = 6 으로 표현 가능

- 아래의 그림과 같이 n! (팩토리얼 연산) 같은 경우에는 12만 돼도 약 5억이기 때문에 대부분 시간 제한을 통과하기 어려움

* O(NlogN) vs O(N^2)

ex) 주어진 배열을 크기 순으로 정렬하는 문제

- N이 1000이하라면 둘 중 어느 것을 쓰더라도 눈깜빡할 사이에 정렬됨

- N이 100만이라면 nlogn은 1초 내로 정렬 완료, n은 정렬이 완료될 때 까지 거의 1시간 걸림

* 공간복잡도

- 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

- 코테에서 별로 신경 안써도 됨

- 이것만 기억해두기 -> 메모리 제한이 512mb일 때 int 변수를 대략 1.2 억개 정도 선언 가능 (int 1개가 4바이트라는 것을 이용해 계산 가능)

- 만약 떠올린 코드가 크기가 5억인 배열을 필요로 하면 해당 풀이는 틀린 코드라는 걸 빠르게 캐치 가능