p.593 시간복잡도 관련 질문입니다.

[PudgeKim]

우선 책의 코드인 while heap 부분을 보면 heap에서 하나씩 뺀걸 insert 함수를 이용하는데 제가 알기로 insert함수는 O(N)의 시간복잡도를 가지고 있으므로 결국 O(N^2)인데

아래는 제가 짠 코드입니다. 저 같은 경우는 정렬 후에 최소값부터 미리 만들어진 리스트에 넣는 식으로 구현하였습니다.
책에서는 heap을 빈 리스트로 선언하고 채워 나가는 식이고 저는 people의 length만큼 -1로 초기화 한 후에 집어 넣는식으로 구현하였습니다.
제가 짠 코드도 결국 O(N^2)이지만 책의 코드 같은 경우는 빈 리스트부터 채워나가니 중간중간 리스트의 적재율이 넘어가면 더 큰 리스트로 바뀌는 오버헤드도 있을거라 제가 짠게 더 빠를거라 생각하였는데
채점을 해보면 제가 짠 코드가 훨씬 느리게 나오는데 이유를 모르겠어서 질문드립니다..
혹시 insert함수도 내부적으로 최적화 같은게 되어있는건가요??

제 코드에 대해 추가 설명을 하자면 최소값부터 정렬이 되있으니 [-1,-1,-1,-1,-1 ..] 이 있을 때 최소값이 (4,4)면 그 앞에 4칸을 비우고 5번째 칸에 (4,4)를 넣고 그 다음 값이 (5,5)면 5칸을 비워놓고 (5,5)를 채우는.. 그런 알고리즘입니다.

    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        answer = [-1] * len(people)
        people.sort()
        
        for j in range(len(people)):
            h, k = people[j]
            for i in range(len(answer)):
                if j == len(answer)-1 and answer[i] == -1:
                    answer[i] = people[j]
                    break
                if k == 0 and answer[i] == -1:
                    answer[i] = people[j]
                    break
                    
                if answer[i] == -1 or answer[i][0] == h:   # answer[i][0] == h 는 앞에 숫자들이 같은경우 대비
                    k -= 1
                else:
                    continue
        
        return answer

[likejazz]

여기서 실행 속도는 시간 복잡도 보다는 모듈의 실행 속도에 훨씬 더 큰 영향을 받습니다.

일반적으로 파이썬 내장 모듈의 실행 속도는 파이썬으로 직접 구현하는 것에 비해 100배 이상 빠른 경우도 많습니다. 왜냐면 파이썬은 모든 것이 객체이기 때문에 불필요한 오버헤드가 많지만 내장 모듈은 C로 꼭 필요한 연산만 수행하고 이 마저도 꾸준히 최적화가 이뤄지고 있기 때문에 매우 빠르게 동작합니다. (p119 동일한 연산의 시간 비교 참고)

책에서는 heapq 모듈에서 거의 모든 연산을 진행한데 반해 제시해주신 코드에서는 직접 파이썬으로 O(n^2) 연산을 수행합니다. 이 경우 시간 복잡도가 아무리 좋아도 파이썬 자체의 느린 속도로 인해 손해를 보는 경우가 많습니다. 만약 모든 코드를 C로 작성한다면 더 빠르게 동작할 수 있겠으나 여기서는 C로 작성된 내장 모듈과 파이썬으로 직접 구현한 알고리즘 간에 기본적인 속도 차이가 존재합니다.