문돌이 존버/프로그래밍 스터디
2021. 6. 23.
알고리즘 복잡도(점근적 복잡도) 기본 개념 다지기
알고리즘의 복잡도란 알고리즘이 소모하는 시간이나 공간을 분석하기 위한 것입니다. 시간과 관련된 것은 시간 복잡도(time complexity), 공간과 관련된 것은 메모리 복잡도(memory complexity)라고 하죠. 최근에는 데이터를 저장할 수 있는 메모리의 발전으로 메모리 복잡도보단 시간 복잡도를 더 중요시하게 여깁니다. 그리고 알고리즘 복잡도는 점근적 복잡도(Asysmptotic Complexity)에 대해서 생각합니다. 이는 곧 정확한 복잡도를 구한다기보다는 입력의 크기가 충분히 클 경우에 대해 생각하는 것입니다. 본 글에서는 크게 3가지를 소개하겠습니다. 1. $O$(빅 오) - 최악의 경우 2. $\Omega$(빅 오메가) - 최상의 경우 3. $\Theta$(빅 세타) - 평균의 경우 ..
