'Algorithm'에 해당되는 글 2건

  1. 2009.04.04 루프 불변성 ( loop invariant )
  2. 2009.03.29 점근적 표기
Programming2009.04.04 16:45
 루프 불변성의 개념이 계속 헷갈린다... for 문에 들어가는 3개의 식과 비슷한 의미 인거 같긴 한데...

이걸 계속 알아보다가 다음의 3개의 글을 찾았다. 루프 불변성에 대해서 알아보고 있다면 다음 글들이 도움이 될것 같다.


http://blog.naver.com/soonchan86/130023452408

http://kin.naver.com/detail/detail.php?d1id=1&dir_id=10104&eid=SNrxjFB+YKL9IbR5XPWfyWcgQZksjxXC&qb=bG9vcCBpbnZhcmlhbnQ=&pid=fnNHoloi5UlssvNPEO0sss--364302&sid=SPc5opUv90gAADcell4

http://en.wikipedia.org/wiki/Loop_invariant

루프 불변성은 알고리즘이 정확한지를 귀납법을 통해서 증명하는 것이라고 한다.

loop를 돌면서 항상 참인 코드가 실행되는것인가 뭐 그런거 같은데...

좀더 알아볼 필요가 있을거 같다
신고
Posted by 초프(초보 프로그래머)
Programming2009.03.29 12:10

f(),g() 는 함수이며, c는 상수이다.

θ(세타) :  g(n)을 f(n)의 점근적으로 정확한 한계(asymptotically tight bound)
θ(g(n)) = {f(n) : 모든 n>=n0에 대해 0<=c1g(n)<=f(n)<=c2g(n)인 양의 상수 c1, c2, n0이 존재 한다}

Ο(빅-오, 오) : 점근적 상한
Ο(g(n)) = {f(n) : 모든 n>=n0 에 대해 0<=f(n)<=cg(n)인 양의 상수 c, n0이 존재한다}

Ω(빅-오메가, 오메가) : 점근적 하한
Ω(g(n)) = {f(n) : 모든 n>=n0 에 대해 0<=cg(n)<=f(n) 인 양의 상수 c,n0이 존재한다}

ο(리틀-오) : 점근적으로 여유있는 상한
ο(g(n)) = {f(n) : 임의의 양의 상수 c>0 에 대해 그리고 모든  n>=n0 에 대해 0<=f(n)<=cg(n)인 양의 상수 n0 이 존재한다}

ω(리틀-오메가) : 점근적으로 여유있는 하한
ω(g(n)) = {f(n) :  임의의 양의 상수 c>0 에 대해 모든 n>=n0에 대해 0<=cg(n)<f(n)인 양의 상수 n0이 존재한다}

신고
Posted by 초프(초보 프로그래머)