네오네오
195
2017-11-13 22:27:02 작성 2017-11-14 11:10:34 수정됨
3
999

파이썬 알고리즘 복잡도가 예상과 다르게 나옵니다


문제는

https://codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

구요.

(문제 안봐도 되지만 참고하시라구)


파이썬의 인덱스 접근연산자를 사용하면 편할 것 같아서

파이썬으로 풀었습니다.



def solution(S, P, Q):
    # write your code in Python 2.7
    dic_key = {'A': 1, 'C': 2,'G': 3,'T': 4}
    
    ret = []
    
    for i in range(len(P)):
        
        hash_str = set([])
        hash_str.update(S[P[i]:Q[i]+1])
        
        list_str = list(hash_str)
        list_str.sort()
        ret.append(dic_key[list_str[0]])
        
    
    return ret



제 생각엔 for문을 한번 돌아서 O(N)이거나

여기에

sort 라이브러리 list 라이브러리 내부 복잡도 때문에

약간의 연산 수가 추가될 것이라고 생각했지만


결과는 O(N*M)이나 나오네요 ㅠㅠ..


(다른 방식으로도 몇 개 바꿔서 풀었는데 결과는 같더라구요. 버그인가..?)


잘 알고 계신 분 없나요??

0
0
  • 답변 3

  • jslovers
    2k
    2017-11-14 01:50:08

    요렇게 해보면 어떨까요?

    def solution(S, P, Q):
    dic_key = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
    ret = []

    for i in range(len(P)):
    ret.append(dic_key[min(list(S[P[i]:Q[i]+1]))])
    return ret
    0
  • 치킨말고개발
    158
    2017-11-14 09:16:53

    질문에 대한 답변은 아니지만


    파이썬 sort 함수가 사용하는 알고리즘 및 시간 복잡도 :

    https://stackoverflow.com/questions/25813774/complexity-of-python-sort-method

    아마도 시간 복잡도가 O(N*M)이 나오는건 이것 때문인것 같습니다.


    저도 파이썬에서 sort함수 자주 사용했는데 무슨 알고리즘일지 한번도 생각해 본적이 없었네요.

    덕분에 이번 기회에 찾아보게 되었습니다. 감사합니다.

    0
  • 네오네오
    195
    2017-11-14 09:35:47

    jhyoon// 오 min을 쓰면 되는군요.

    그런데.. 복잡도는 똑같이 나오네요 ㅠㅠ

    0
  • 로그인을 하시면 답변을 등록할 수 있습니다.