p. 307: `31. 상위 K 빈도 요소` - 최적화 & 파이써닉한 코드 질문

[nayeonshin]

p. 307: `31. 상위 K 빈도 요소` - 최적화 & 파이써닉한 코드 질문

[likejazz]

안녕하세요~

책에서도 여러 차례 언급하고 있지만 log는 마법과 같은 함수라서 로그 뒤에 위치한 값이 무엇이느냐는 성능에 전혀 영향을 주지 않습니다. 왜냐면 log(1억)도 27도 채 안되기 때문이죠. 즉 n log(n)이나 n log(k)는 사실상 같다고 할 수 있습니다. 따라서 실무에서는 의미가 없다고 할 수 있고, 하지만 구두로 코딩 인터뷰를 진행할 때는 면접관에게 이 같은 내용을 설명할 수 있다면 당연히 더 좋은 인상을 줄 수는 있을 것 같습니다.

아울러 리스트 컴프리헨션으로 표현하니 훨씬 더 가독성이 좋은거 같네요. 감사합니다!

[nayeonshin]

안녕하세요 @likejazz 님 답변 감사합니다! 이해가 잘 되었어요.

한 가지 더 질문이 있어요. 여기서 O(n log n) 풀이를 O(n + k log n)으로 최적화하는 것은 "실무에서도 의미"가 있을까요?

답을 찾기 위해 시도해본 것

is "k log n" smaller than "n log n" in big o for k <= n이런 키워드로 구글링을 해보고, 몇 개 없는 관련 검색 결과 중 스택오버플로우 글 몇 개를 읽어봤는데: 글 1, 글 2 약간 상충되는 내용이 있는 것 같아서 헷갈립니다. 👇

글 1 답변: "O(n + (k log n)) is approximately O(n)" (제 해석: O(n + (k log n)) ≈ O(n))
vs.
글 2 답변: "Which is "better" is therefore unclear, although my quick analysis tended to show that O(n + k log n) performs better under mild assumptions on k." (제 해석: "결국 O(n + k log n)과 O(n log n) 중 어떤 것이 더 나은 지는 불분명하다")

---

최대힙을 사용하는 책의 코드에서 로그 앞에 있는 계수를 최적화할 수 있는 방법(O(n log n) 풀이를 O(n + k log n)로)을 생각해봤어요.

책의 코드는 비어있는 리스트를 먼저 선언하고, 힙(리스트)에 요소를 하나씩 삽입하면서 힙을 쌓아가기 때문에 최종적으로 이 풀이의 시간 복잡도는, n이 len(nums)일 때, O(n + n log (n) + k log (n)) = O(n log (n)) ➡️ 아래 코드 항목 참조
(문제에 k는 최대 n이라는 constraint이 존재하기 때문에 O(k log (n)) <= O(n log (n)), 따라서 단순히 O(n log (n)으로 표기 가능)이지만,

힙에 요소를 하나씩 넣는 것 대신 heapify()를 사용하면 힙을 만드는 시간 복잡도가 O(n log n)에서 O(n)으로 줄기 때문에, 총 시간 복잡도가 O(n + n + k log (n)) = O(n + k log (n))입니다. 여기에다가 사소한 edge case인 if k == len(nums): return nums 체크를 통해 k == n인 경우를 미연에 방지하여 k가 n보다 엄격히 작을 수 있도록 보장한다면,
이런 O(n log (n) ⇒ O(n + k log (n)) 시간 복잡도 최적화가 의미가 있다고 볼 수 있을까요? (이런 최적화가 "polynomially dominating"하는 항을 최적화하는 것일까요?)

코드

책에 있는 원래 코드

def topKFrequent(self, nums: List[int], k: int) -> List[int]: freqs = collections.Counter(nums) # O(n) 시간 & O(n) 공간 (여기서 `n`은 len(nums)) freqs_heap = [] for f in freqs: # ⭐ 힙에 요소를 하나씩 삽입함으로써 최대힙을 쌓기 때문에 O(n log n) 시간 heapq.heappush(freqs_heap, (-freqs[f], f)) # `freq_heap`: O(n log n) 시간 & O(n) 공간

    topk = list()
    for _ in range(k):
        # 아웃풋 리스트인 `topk`를 공간 복잡도 계산에 고려하지 않았을 때, O(k log n) 시간 & O(1) 공간
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

👇

heapify()를 사용해 최적화한 코드

def topKFrequent(self, nums: List[int], k: int) -> List[int]: if len(nums) == k: # ⭐ 최적화 방법: edge case 체크하여 k < n을 엄격히 보장 return nums

    freqs = collections.Counter(nums)  # O(n) 시간 & O(n) 공간 (여기서 `n`은 len(nums))
    
    # ⭐ 최적화 방법: 미리 튜플 리스트를 만들고 heapify()를 한번에 하기 -- O(n) 시간 & O(n) 공간 =====
    freqs_heap = [(-freqs[f], f) for f in freqs]  # O(n) 시간 & O(n) 공간
    heapify(freqs_heap)  # O(n) 시간 & O(1) 공간
    # ==========

    topk = list()
    for _ in range(k):
        # 아웃풋 리스트인 `topk`를 공간 복잡도 계산에 고려하지 않았을 때, O(k log n) 시간 & O(1) 공간
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

제 질문이 별로 중요하지 않은 질문일 수도 있지만, 긴 글 읽어주셔서 정말정말 감사합니다!

+) 코드 섹션 HTML 렌더링이 약간 이상하게 되네요. 이해 부탁드립니다. ㅠㅠ