Codility 성능 차이는 : 해시

Question

대 배열은 내가 codility에서 시험을했다 : https://codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 나는 두 개의 서로 다른 솔루션 사이의 성능 차이주의 :

1 - 목록 솔루션 :

def solution(list) 
    unmatched_elements = [] 
    list.each{ |el| 
    if unmatched_elements.include? el 
     unmatched_elements.delete el 
    else 
     unmatched_elements.push el 
    end 
    } 
    unmatched_elements[0] 
end 

2 - 해시 솔루션

을

def solution(a) 
    unmatch = {} 

    a.each do |e| 
    if unmatch[e].nil? 
     unmatch[e] = 1 
    else 
     unmatch.delete e 
    end 
    end 
    unmatch.keys.first 
end 

첫 번째 시도는 일부 시간 초과로 25 %의 성능 점수를 받았습니다. 두 번째 것은 100 % 성능 점수를주었습니다. 왜 그런가요? 나는 해시로 밀어 넣기 만하면 O (n)의 공간 복잡성이 목록과 같은 결과를 낳 겠지만 그렇지 않은 것 같다. 왜 그런가?

Answer 1

그것은 공간의 복잡성에 관한 것이 아니라 시간 복잡성에 관한 것입니다. 특히, 배열 (include?)에서 요소를 찾는 것은 일치 할 때까지 각 요소를 검사해야하기 때문에 N 시간 작업입니다. 해시 조회 []은 일정한 시간입니다. 그것이 말하는 시험 조건에서 https://stackoverflow.com/a/4363602/1034681