'오메가표기법'에 해당되는 글 1건

알고리즘의 성능분석은 어떻게 하는 것일까?

만약 기존에 있는 알고리즘을 개선해서 어떠한 알고리즘을 새로 만들었고,

알고리즘이 내 PC에서 결과가 나오는데 까지 2초가 걸렸다고 주장한다면, 그 주장을 믿을 수 있는 것일까?

현실적으로 서로 다루는 PC의 사양과 환경, 소프트웨어 등이 전부 다르므로 알고리즘을 정확히 측정하기 힘들다.

이를 공정하게 비교하기 위해서 점근적 표기법을 사용한다.

점근적 표기법은 3가지가 존재한다.

O-notation (빅오 표기)

Ω-notation (오메가 표기)

Θ-notation (세타 표기)

이 3가지 방법에 대해서는 다음 포스팅에서 알아보도록 하자