핵심
데이터가 늘어나도 버틸 수 있나요?
나는 지금 앰진이다.
시간 복잡도
- 입력 데이터(N)이 증가할 때 연산 횟수가 어떤 비율로 증가하는가를 나타내는 개념
- “증가하는 추세”를 나타냄
Big-O
Info
시간 복잡도의 증가율을 표현하는 수학적 표기법
입력 크기가 증가할 때, 수행 시간의 상한을 나타냄
알고리즘의 수행 시간이 입력 크기에 따라 어떻게 증가하는 지를 O(N) 형태로 나타냄
O(1) VS O(N)
O(1) : 항상 걸리는 시간이 똑같음
- 배열 특정 인텍스 접근, 해시맵 검색
O(N) : 입력이 늘어나는 만큼 시간도 정비례해서 늘어남 - for문으로 배열 전체를 처음부터 끝까지 실행
O(N²)
이중 for문
O(log N)
반씩 줄어다는 연산
- 이진탐색, DB의 B-Tree 인덱스 스캔
실무에서 O(1)이 무조건 빠른건 아님
-
실제로 데이터를 불러올때의 걸리는 시간을 측정해봐야함
-
실무에서는 알고리즘의 시간복잡도 뿐만아니라, I/O까지 확인해야함