장민석
가입: 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초도 안 돼서 답이 튀어나옵니다. 최적화 방법을 잘 생각해 봐야겠네요. |
|