강의 "복잡도"는 자원이 얼마나 필요한가를 나타내는 측도입니다. - 시간 복잡도 : 문제의 크기와 해결하는데 걸리는 시간 사이의 관계 - 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계 "시간 복잡도"에는 여러 가지 종류가 존재합니다. - 평균 시간 복잡도 : 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 - 최약 시간 복잡도 : 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 복잡도를 표기할 때, 점근 표기법 중에 하나인 "Big-O Notation"을 이용합니다. - 선형 시간 알고리즘 O(n) : 선형 탐색 - 로그 시간 알고리즘 O(log n) : 이진 탐색, 병합 정렬(O(nlog n)) - 이차 시간 알고리즘 O(\(n^2\)) : 삽입 정렬