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