6강 요약

시간복잡도는 여러가지 기준에 따라 구분이 있다.
시간에 따라 구분 할 것인지 <-> 공간에 따라 구분 할 것인지
평균 시간에 따를 것인지 <-> 최악의 시간에 따를 것인지

내용

용어 정리

시간복잡도(Time Complexity) : 문제의 크기와 이를 해결하는데 걸리는 시간 간의 관계

공간복잡도(Space Complexity) : 문제의 크기와 이를 해결하는데 필요한 메모리 크기 관계

평균 시간 복잡도(Average Time Complexity) : 임의 패턴에서 소요되는 시간의 평균

최악 시간 복잡도(Worst-case Time Complexity) : 시간이 가장 오래 걸리는 패턴에서 소요되는 시간

Big-O Notation : 어떤 함수의 증가양상을 다른 함수와의 비교로 표현(입력 크기가 N일때 걸리는 시간)

대표적인 복잡도

선형 탐색(Linear Search) : O(n)

이진 탐색(Binary Search) : O(log n)

삽입 정렬(Insertion Sort) : O(n2)

병합 정렬(Merge Sort) : O(n log n)