Q&A와 스터디
복학해서 알고리즘을 듣고 있는데
첫번째 시험에서 완전히 발렸습니다.
O(n) 을 구하는 거였는데
저는 이때까지 코드 보고 루프의 형태를 대충 보고 n의 제곱이다 n로그n 이다. 이렇게 했었는데.
교수님이 수학적으로 접근을 해서 일반항을 구한 다음 어찌어찌 하시니까 빅오의 일반항이 나오더군요
책에 써있는 대로 수식을 만들어보려고 했지만 중간 중간 갑자기 생략이 되어서 뭐가 뭔지 모르겠습니다.
대학수학책을 찾아보고 수1 개념원리 까지 찾아 봤지만
알로리즘의 일반항이 특수한 경우가 많아서 대부분의 경우 적용이 안되더군요
주로 알고리즘 성능에 관계되어서 어떤학문을 공부해야 할까요?
그리고 대표적인 알고리즘(피보나치, 팩토리얼 등등.)의 성능을 측정하는 일반항 만드는 방법을 비교적 자세히 알 수 있는
자료같은것좀 있으면 추천좀 해 주세요
(참고로 학교 교재가 한빛 출판사의 알기쉬운 알고리즘 입니다...(쉽기는 개뿔..) )
첫번째 시험에서 완전히 발렸습니다.
O(n) 을 구하는 거였는데
저는 이때까지 코드 보고 루프의 형태를 대충 보고 n의 제곱이다 n로그n 이다. 이렇게 했었는데.
교수님이 수학적으로 접근을 해서 일반항을 구한 다음 어찌어찌 하시니까 빅오의 일반항이 나오더군요
책에 써있는 대로 수식을 만들어보려고 했지만 중간 중간 갑자기 생략이 되어서 뭐가 뭔지 모르겠습니다.
대학수학책을 찾아보고 수1 개념원리 까지 찾아 봤지만
알로리즘의 일반항이 특수한 경우가 많아서 대부분의 경우 적용이 안되더군요
주로 알고리즘 성능에 관계되어서 어떤학문을 공부해야 할까요?
그리고 대표적인 알고리즘(피보나치, 팩토리얼 등등.)의 성능을 측정하는 일반항 만드는 방법을 비교적 자세히 알 수 있는
자료같은것좀 있으면 추천좀 해 주세요
(참고로 학교 교재가 한빛 출판사의 알기쉬운 알고리즘 입니다...(쉽기는 개뿔..) )
2008.09.20 00:26:08 (*.186.153.9)
![[레벨:4]](http://old.lameproof.com/modules/point/icons/default/4.gif "포인트:1540point (12%), 레벨:4/30"){kind=icon}
갱훈 아잉잉♥님~ 우선 답변 갑사드립니다. 그런데, PKI 이라고 하는 것은 전자상거래 암호화 하는 쪽을 말씀하신 건가요? 구글님에게 물어보니 그쪽만 나오는데.. 저는 그 뭐냐 컴퓨터 공학쪽에서 소프트웨어의 성능을 분석 할 때 쓰이는 일반항을 유도 할 수 있을만한 능력이 제게는 없기 때문에 이쪽 분야에 관한 전문적인 학문이 분명히 있을 것 같아서... 키워드라도 좀 알고 싶어서 이렇게 굽신굽신 하는 겁니다. 저의 질무닝 뭔가 부정확 한것 같아서요 ㅋㅋ 이렇게 보충 설명 합니다.
2008.09.20 21:08:52 (*.118.156.254)
![[레벨:2]](http://old.lameproof.com/modules/point/icons/default/2.gif "포인트:535point (38%), 레벨:2/30"){kind=icon}
아잉잉♥ 저는 pki쪽 공부하시면 암호화 복호화 알고리즘에 대한 좀 자세히 알게 될수 있을가 해서요 ^^
알고리즘에 대해서 아직 자세히 모르신다면 정보처리 기사 알고리즘 부분 한번 보세요.
알고리즘 성능 및 개선에 대해서도 나와요. 정보처리 기사 알고리즘에 나오는 부분을 이해해서
순서도도 그리고 직접 프로그램으로 작성해 보면 도움이 될꺼 같습니다. 그리고 학생때 진짜
시간이 많으시면 The art of computer programming 이란책을 배우면 도움이 많이 된다고
하는데 회사 가보니깐 그런것 보다 리눅스 명령어 몇자나 업무파악 vi, 이클립스가 훨씬
도움이 되는것 같네요.
알고리즘에 대해서 아직 자세히 모르신다면 정보처리 기사 알고리즘 부분 한번 보세요.
알고리즘 성능 및 개선에 대해서도 나와요. 정보처리 기사 알고리즘에 나오는 부분을 이해해서
순서도도 그리고 직접 프로그램으로 작성해 보면 도움이 될꺼 같습니다. 그리고 학생때 진짜
시간이 많으시면 The art of computer programming 이란책을 배우면 도움이 많이 된다고
하는데 회사 가보니깐 그런것 보다 리눅스 명령어 몇자나 업무파악 vi, 이클립스가 훨씬
도움이 되는것 같네요.
2008.09.20 22:16:34 (*.130.9.14)
![[레벨:0]](http://old.lameproof.com/modules/point/icons/default/0.gif "포인트:10point (11%), 레벨:0/30"){kind=icon}
김민성 위에분이 말씀하신데로 the art of computer programming 1권 앞부분을 보시면 되겠네요...
2008.09.21 07:53:27 (*.106.61.128)
ddy 문제가 분할되는 문제의 경우, master method라는 이름으로 수식으로 정리된 시간 복잡도 계산법이 있습니다.
일반적인 문제는 대부분 루프의 깊이를 따르는거 같습니다(제 생각엔:$)
때로 잘 생각해보면 루프의 깊이보다 작을수가 있는데 분할상환분석법(정확한 이름이 기억안나네요)이라는 챕터를 읽어보세요
예로, 어느 트리에서 모든 노드에 대해, 그 노드의 자식들을 다 살펴보는 일을 수행한다면 루프가 이중이기 때문에 O(|V|^2)의 시간이
걸릴거같지만 루프 안의 문장들이 수행되는 횟수는 루트를 제외한 모든 노드들에 대해 수행되므로 O(|V|)시간이라고 볼수있죠.
일반적인 문제는 대부분 루프의 깊이를 따르는거 같습니다(제 생각엔:$)
때로 잘 생각해보면 루프의 깊이보다 작을수가 있는데 분할상환분석법(정확한 이름이 기억안나네요)이라는 챕터를 읽어보세요
예로, 어느 트리에서 모든 노드에 대해, 그 노드의 자식들을 다 살펴보는 일을 수행한다면 루프가 이중이기 때문에 O(|V|^2)의 시간이
걸릴거같지만 루프 안의 문장들이 수행되는 횟수는 루트를 제외한 모든 노드들에 대해 수행되므로 O(|V|)시간이라고 볼수있죠.
2008.09.21 10:18:59 (*.37.69.154)
갱훈 답변들 정말 감사 드립니다. 아직 대학생이다 보니 이론적으로 또 수학적으로 배울 수 있는 것들은 다 배우고 싶어서 이렇게 방황을 하고 있습니다.
여러분들이 답변주신 내용들 다 찾아 보고 유효한것들이 있으면 흡수하도로록 해야겟네요~ ^^
여러분들이 답변주신 내용들 다 찾아 보고 유효한것들이 있으면 흡수하도로록 해야겟네요~ ^^
2013.05.19 13:13:25 (*.153.235.115)
![[레벨:3]](http://old.lameproof.com/modules/point/icons/default/3.gif "포인트:962point (24%), 레벨:3/30"){kind=icon}
bestbasci01@yahoo.com
