시간복잡도 계산 Big O 표기법

개념

참조 링크
https://noahlogs.tistory.com/27
https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/

시간복잡도를 분석한다는 것은 알고리즘이 문제를 해결하는데 있어서
얼마나 오랜 시간이 걸리는지 분석하는 것이다.

그 중 Big O 표기법은 알고리즘 효율성을 상한선 기준 (최악의 상황) 으로 보기때문에
문제를 풀때 타임아웃을 피하려면 최악의 상황을 고려해서 설계를 해야한다.

알고리즘 예제

1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2ⁿ) : 피보나치 수열

출처: https://noahlogs.tistory.com/27 [인생의 로그캣]

성능비교