강의로 돌아가기
김튀김

두 코드의 효율 비교 (답이 있으니 원치 않으시면 보지 마세요!)

두 코드 중 첫번째 코드는 효율성 테스를 통과하고, 두 번째 코드는 통과 못 했습니다.
근데 제 생각에는 두 번째 코드가 더 효율적인 거 같아요.
왜 첫번째 코드 효율성이 더 좋은지 알려주세요,,ㅠㅠ

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i,j in zip(participant,completion) :
        if i != j :
            return(i)
    return participant[-1]
def solution(participant, completion):
    for i in participant :
        try :
            completion.remove(i)
        except :
            return i
  • 정봉수
    혹시 왜그런지 찾으 셨나요?? 저도 두번째 코드가 나은거 같은데 왜그런지를 모르겠어요 정봉수 2019.02.14 14:35
  • 정병창
    첫번째는 O(n)이고 두번째는 O(n^2)여서 그런것같아요 두번째는 for문이 n Time complexity이고 remove도 n이기 때문에 그런거죠 정병창 2019.03.24 15:14
1 개의 답변
Demi

안녕하세요

파이썬에서 리스트의 remove연산은 시간복잡도가 O(n)입니다. 따라서

  • 첫번째 코드의 시간복잡도는 소팅때문에 O(nlogn) 이며
  • 두번째 코드의 시간복잡도는 O( n2 ) 입니다. - for문에서 n, remove에서 n이 걸림
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.