|
:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
16/04/07 13:35
Big-O Notation은 일반적으로 Input Size에 따라 알고리즘의 실행시간이 어떻게 바뀌는지를 대략적으로 표시해줍니다.
O(x)라면 input의 크기가 커짐에 따라 그 실행시간이 linear하게 커진다고 할수 있죠. O(1)은 Constant time입니다. 즉 어떤 O(1)인 알고리즘은 Input x의 크기가 어찌되었든 동일한 시간에 결과를 내줍니다. Small-O는 다음분께..
16/04/07 13:40
제가 책내용의 흐름이 어떻게 되는지 몰라서 틀릴수도 있겠지만, 결국 Big-O notation 쓴다는건 running time을 비교하겠다라는 거라서 차이가 없을거 같습니다. 쓰고 보니 저도 공부하는 내용이라 자신이 없긴 하네요 흐...
16/04/07 14:22
컴공 알고리즘 수업에서는 윗분 말씀이 맞고, 교재에서도 그렇게 설명합니다. 수학 과목에서의 Big-oh notation은 주로 테일러 급수와 세트로 나오는 경우가 많은데, remainder를 복잡하게 쓰기 귀찮으니 저걸로 퉁치자..라고 보시면 되겠습니다.
Big-oh notation은 상한 점근, 즉 수학식으로 표현하면 두 함수 f(x), g(x)가 있고 x가 무한대로 갈 때 lim|f(x)/g(x)|<∞ 이면 f(x)=O(g(x)) 가 되고 이걸 다시 쓰면 |f(x)|<C|g(x)|가 됩니다. 이걸 다시 말하면 f(x)는 무슨 짓을 해도 g(x)의 상승률을 추월할 수 없다는 뜻이 됩니다. Small-oh notation은 Big-oh notation과 반대로 x가 무한대가 아닌 0으로 수렴할 때를 생각하시면 됩니다. 즉, Big-oh 에서 lim|f(x)/g(x)|<∞ 이었던게 Small-oh 에서는 lim(f(x)/g(x))=0 이 되겠죠. 는 써놓고 본문 다시 보니 같은 설명이 있네요 이런..-_-;; 헷갈리시는 부분이 등호 때문인 것 같은데, 저 등호를 ∈ 로 바꿔서 보시면 좀더 이해가 잘되실겁니다. 서론이 길었는데.. 암튼 사진의 수식에 대해 설명하면, Big/Small-oh notation의 production rule 중에 fO(g)=O(fg)가 있습니다. 4줄로 된 수식의 두번째줄에서 세번째줄로 넘어갈 때 이 법칙이 적용된거구요, o(x^2)O(x^-1)=o(x) 의 경우에도 마찬가지지만 x가 0으로 가기 때문에 small-oh를 택해 o(x)가 됩니다. 아래에 따로 있는 수식의 변형도 같은 원리구요. o(1)+O(1)+o(x) -> O(1) 과 O(x)=o(1) 이 부분은, 위에서 말씀드린 lim(f(x)/g(x))=0 를 놓고 생각하시면 편합니다. 즉, o(1)+O(1)+o(x) -> O(1) 의 경우 o(1)과 o(x)는 뭔짓을 해도 O(1)을 추월할 수 없습니다. 때문에 Big-oh notation에서는 o(1)과 o(x)를 날려버리고 O(1)만 남겨놓을 수 있게 되는 거구요, 아래 수식에서의 O(x)=o(1)의 경우 1/x=o(1) 만 써도 충분할거 같은데 굳이 늘려서 왜 혼동을 주는지 잘 모르겠으나..-_-;; 바로 위에 말씀드린걸 뒤집어서 생각해보시면 이해가 편할 것 같습니다. 사족으로, 아래에 잘려서 나오는 테일러 급수의 경우 O(x^3)를 오차항이라고 교수님께서 설명하셨을텐데, e^x=1+x+x^2/2+x^3/3+... 에서 오차항으로 e^x−(1+x+x^2/2) 가 묶이고, 이건 x가 0으로 갈 때는 뭔짓을 해도 |x^3|을 넘을 수 없기 때문에 오차항은 O(x^3)로 바꿔서 표기할 수 있습니다. 설명이 좀 횡설수설한 것 같은데.. 이해 안되시면 말씀해주세요. 다시 보다 쉽게 말씀드리곘습니다. 중간고사 화이팅이에요..
16/04/07 14:47
x가 0으로 가는 경우에는 어차피 0으로 수렴할 때의 asymptotic behavior만 중요하므로
x를 1보다 항상 작다고 생각하시면 편합니다. 즉 (대략) x^3 < x^2 < x < 1 < x^-1 < x^-2 < x^-3... 이라고 보시면 됩니다. x->0 인 경우 big-O, small-O notation의 엄밀한 정의는 아래와 같은데요, - f(x) = O(g(x)) <=> f(x)/g(x) -> C as x->0 (C는 0일 수도 있고 무한일 수는 없음) - f(x) = o(g(x)) <=> f(x)/g(x) -> 0 as x->0 사실 그냥 f(x)<=g(x)(작거나 같다)이랑 f(x)<g(x)(작다)정도로 "직관적으로" 생각하시는 게 편합니다. 즉 f(x) = O(1)이라고 하면 f(x)의 x->0으로 갈때의 추세는 1(혹은 상수)보다 작거나 같구나~ 라고 생각하는 겁니다. (물론 엄밀하게 증명해보시는 것도 좋은 훈련이 됩니다.) x^-2*o(x^2) = x^-2 * (x^2보다 작은 거) = (1보다 작은 거) = o(1) x*O(x^-1) = x * (x^-1보다 작거나 같은 거) = (1보다 작거나 같은 거) = O(1) 마지막줄의 o(1)+O(1)+o(x)은 (1보다 작은 거)+(1보다 작거나 같은거)+(x보다 작은 거) 인데, 위에서 보셨듯이 x<1이므로 (1보다 작은 거)+(1보다 작거나 같은거)+(x보다 작은 거) <= 1 이겠죠? 그래서 3개를 합하면 O(1)이 됩니다. 마찬가지로 x*O(1) = O(x)인 것은 설명해드리지 않아도 될 것 같고, x<1이기 때문에 O(x) = o(1)이 되죠. x보다 작거나 같은 거는 항상 1보다 작을테니까요. 더 궁금하신 거 있으시면 쪽지 주세요.
16/04/10 12:18
과제에 치이다가 뒤늦게 확인했습니다 흑흑.
답변주신분들 너무 감사합니다! 천천히 읽어보고 이해안되는 부분있으면 염치불구하고 쪽지드리겠습니다.
|
||||||||||||
