알고리즘 분석에 대한 질문입니다.

orion7의 이미지

안녕하세요.

혹시 알고리즘 속도를 나타내는 표기법인 'O' 빅오 표기법에 대해 잘아시는 분 있나요?

지금 논문을 쓰고 있는데, 속도 관련해서 표시를 해야될것 같은데...

한부분에서 막혀서 도저히 진도가 나가지를 않네요...

 
 
for i in range(n) : 
  for j in range(n) : 
    if   조건  : 
      break 
 

이러한 형태로 되어있으면 빅오 표기법으로 어떻게 되나요?
아니면 빅오 관련해서 잘 되어있는 사이트 아시는 분 좀 알려주세요.

중간에 조건문이 있어서 중간에 빠져 나가게 되면 어떤 형태로 표기가 되는지
궁금하네요.

이부분때문에 논문을 쓰다가 막혀서... 정말 답답하네요

M.W.Park의 이미지

최적, 평균, 최악으로 세분하기도 합니다만,
보통은 평균 성능을 표기하는 것으로 알고있습니다.

계산법은 구글링하시면 많이 나옵니다.

예시하신 코드만 보고서는 최악 O(n^2), 최적 O(n) 정도가 될거같다는 추측밖에 못하겠군요.

-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂

-----
오늘 나의 취미는 끝없는, 끝없는 인내다. 1973 法頂

ckebabo의 이미지

O(n^2)

복잡도 함수 f(n)이 있을 때 g(n) <= c*f(n)을 만족하면 g(n)이 O(f(n))에 속한다고 할 수 있습니다.