Big O 착각

http://theyearlyprophet.com/big-oh-time-complexity.html

알고리즘 성능평가 이야기가 있길래
찾다보니 제가 알고 있는 Big O 에 대한 지식이 좀 잘못되었었네요.

Worst O(n), Avg O(n), Best O(n), Armotized O(n) 은 별개라는..

잡담 | 1639명이 읽었어요. 18.119.163.14

비공개 손님 … 2015-01-07 05:35:34

이런 분류도 있군요

으음... 그러고보니
저 배울땐 빅오=상한, 빅오메가=하한, 빅세타=평균으로 배웠던 거 같기도 한데
(정확히 이야기하자면 걍 빅오의 경우 해당 곡선 이하로 나온다 뿐이니까 뭐..관련없나 ㅜㅜ)

비공개 손님 … 2015-01-07 09:46:48

빅오 노테이션의 정의는 함수 f(x), g(x) 에 대하여 lim (x-> 무한대) f(x)/g(x) 가 수렴하여 값을 가지면 f = O(g) 라고 쓰는거라, 애초에 함수들의 인자인 x가 '큰 수'라고 가정하는 거라 저런 이야기가 나오는 듯. 보통 x가 시간이니 알고리즘 돌아가는데 엄청나게 많은 시간이 걸릴 경우 성립하는 이야기.

비공개 손님 … 2015-01-07 16:11:00

2 / 그래서 stackoverflow 같은데 보면 Amortized O 를 종종 이야기 하더라구요.

댓글을 작성하실 수 없습니다.
(권한이 없는 회원레벨)

목록으로

△ 이전글: C 언어 몇가지 질문! 코드멍키님 관심 좀. [11]

▽ 다음글: 프로그램 용어 질문 [4]

TOP arrow_upward