매일매일 알고리즘 공부/알고리즘 개념

빅오 표기법 빅오 표기법은 점근적 실행 시간을 표기할 때 가장 많이 사용하는 수학적 표기 방법으로, 점근적 실행 시간이란 n이라는 입력값이 무한대로 커질 때의 실행 시간 추이를 의미한다. 점근적 실행 시간을 달리 말하면 '시간 복잡도' 라고 할 수 있다. 빅오 표기법은 알고리즘 최악의 실행 시간을 표기하며, 가장 많이 사용하는 표기법이다. 빅오 표기법은 왼쪽에서 오른쪽으로 갈수록 효율성이 좋아진다. ( O(1) 이 가장 빠름 ) 차례대로 지수함수, 다항함수, 선형함수, 로그함수, 상수함수를 의미한다. 1. O(1) : 스택에서 push, pop 2. O(log n) : 이진트리 3. O(n) : for 문 4. O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬 5. O(n^2) : 이중 for 문, ..