Algorithm | 빅오 표기법

시간 복잡도

• O(1): 단순 연산
• O(n): for문
• O(n^2): 중첩 for문
• O(logn): 1과 가까워서 시간 복잡도 효율성이 높다.
• O(nlogn): n^2보다 시간 복잡도 효율성이 조금 더 낫다.

공간 복잡도

• O(1): Boolean, null, undefined, 상수를 할당하는 변수
• O(n): string의 길이, 배열의 길이 등을 다룰 때

객체 vs 배열

객체

• 객체는 순서가 없다.
• O(1): 접근, 추가, 삭제
• O(n): 탐색

배열

• 배열은 인덱스라는 순서를 갖는다.
• O(1): 배열에 값을 추가, 끝 부분에 값을 추가/삭제(push, pop)
• O(n): 시작부분에 값을 추가/삭제(unsifht/shift), 대부분 n의 복잡도를 갖는다.