알고리즘 분석에 대한 질문입니다.
글쓴이: orion7 / 작성시간: 화, 2008/08/26 - 4:58오후
안녕하세요.
혹시 알고리즘 속도를 나타내는 표기법인 'O' 빅오 표기법에 대해 잘아시는 분 있나요?
지금 논문을 쓰고 있는데, 속도 관련해서 표시를 해야될것 같은데...
한부분에서 막혀서 도저히 진도가 나가지를 않네요...
for i in range(n) :
for j in range(n) :
if 조건 :
break
이러한 형태로 되어있으면 빅오 표기법으로 어떻게 되나요?
아니면 빅오 관련해서 잘 되어있는 사이트 아시는 분 좀 알려주세요.
중간에 조건문이 있어서 중간에 빠져 나가게 되면 어떤 형태로 표기가 되는지
궁금하네요.
이부분때문에 논문을 쓰다가 막혀서... 정말 답답하네요
Forums:
최적, 평균, 최악으로
최적, 평균, 최악으로 세분하기도 합니다만,
보통은 평균 성능을 표기하는 것으로 알고있습니다.
계산법은 구글링하시면 많이 나옵니다.
예시하신 코드만 보고서는 최악 O(n^2), 최적 O(n) 정도가 될거같다는 추측밖에 못하겠군요.
-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂
-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂
O(n^2) 복잡도 함수
O(n^2)
복잡도 함수 f(n)이 있을 때 g(n) <= c*f(n)을 만족하면 g(n)이 O(f(n))에 속한다고 할 수 있습니다.
댓글 달기