컴퓨터공학1 Algorithm Analysis 1 (Big-θ, Big-O, Big-Ω Notation) 우리는 알고리즘의 성능을 분석하기 위해 해당 알고리즘의 수행시간을 구하여 직접 비교할 수 있다. 하지만 알고리즘의 정확한 수행시간은 보통 알아내기 힘들뿐더러, 설사 알아낼 수 있다고 하더라도 일반적으로 굳이 시간을 계산할 수고를 할 필요가 없다. 그 이유는 입력이 충분히 커진다면 특정 수행시간에서 상수 계수와 상대적인 저차항은 입력의 크기에 묻혀버리기 때문이다. 그럼 우리가 알고리즘의 성능을 분석하기 위해 사용할 수 있는 개념에는 어떤 것이 있을까?점근적 표기법 (Asymptotic notation) 일반적으로 알고리즘의 수행시간을 나타낸다고 할 때는 입력의 크기가 매우 큰 경우에 대해 알아보려는 것이다. 즉, 점근적 표기란 입력의 크기가 \(n\)일 때, \(n\rightarrow\infty\)인 경우.. 2024. 4. 28. 이전 1 다음
