게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

2-2 time complexity

 
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.210 Principles of Programming (Spring 2007)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
장민석



가입: 2006년 9월 5일
올린 글: 165

올리기올려짐: 2007년4월25일 12:40    주제: 2-2 time complexity 인용과 함께 답변

실습시간에 조교님의 질문에 잘못 대답드린 것 같네요. 수행시간이 plus 회수에 exponential하게 비례합니다. 알고리즘을 생각해보면 당연한 건데..;;

코드:
(myMatch '(1 0) (plus (plus (plus (plus (plus (plus (plus (plus (plus (plus (plus (plus (plus (atom 0)))))))))))))))


plus 13개: 1초 미만

계속 실험을 해봤더니
plus 14개: 약 2초
plus 15개: 약 6초
plus 16개: 약 18초

뭐 이런 식이네요...

음 수행시간을 줄일 수 있는 방법이 있을지 궁금하네요. 직관적으로 생각하면 없을 것 같은데, 닥터스킴은 분명 훌륭한 정규 표현식 라이브러리를 제공하고 있거든요. 역시 실험을 해봤더니,,

코드:
(regexp-match (regexp "((((((((((((((((((((a+)b+)c+)d+)e+)f+)g+)a+)b+)e+)s+)e+)b+)e+)r+)a+)d+)c+)c+)d+)e+") "adbjiejifihihefkadhkvhdgiejfiejfiejgidkafheiojfgiekjgidhgoqhkvndkvhjirejflijeifjelfoeifhieh")

#f

1초도 안 돼서 답이 튀어나옵니다. 최적화 방법을 잘 생각해 봐야겠네요.
위로
사용자 정보 보기 비밀 메시지 보내기
공순호



가입: 2005년 9월 29일
올린 글: 363
위치: 302동 312-2호

올리기올려짐: 2007년4월25일 17:39    주제: 인용과 함께 답변

교수님께 여쭤보고 진행할 계획이지만,

Time Complexity가 더 좋은 코드에 대해서는 보다 좋은 점수를 주었으면 하는 것이

제 생각입니다. (그렇다고 Delay하시지는 마시고요..)
_________________
- soon@ropas
위로
사용자 정보 보기 비밀 메시지 보내기 글 올린이의 웹사이트 방문
이전 글 표시:   
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.210 Principles of Programming (Spring 2007) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay