levelorder 방식과 postorder 방식에서의 시간복잡도... - 인프런

코딩테스트 [ ALL IN ONE ]

[코테 적용] 👉 level order traversal (후반부)

levelorder 방식과 postorder 방식에서의 시간복잡도에 관해 질문이 있습니다.

해결된 질문

작성

223

강사님께서는 어짜피 둘다 모든 노드를 순회해야 하기 때문에 최악의 경우에도 시간복잡도가 O(N)이라고 하셨습니다. 그런데 아래와 같이 leetcode에 제출한 결과 런타임이 다르게 나와서 의문이 들었습니다.

위가 postorder고, 아래가 levelorder인데 왜 levelorder가 더 빠른건가요?? 아니면 시간복잡도는 대략적으로 계산한 결과이기 때문에 실제 런타임을 돌린 결과에서는 상수값의 차이가 나서 저런 결과가 나온건가요??

답변 1

지식공유자

안녕하세요 앰비션님!

저정도 시간차이면 거의 시간차이가 없다고 보셔도 됩니다.

동일한 코드를 몇번 실행해보면 그때마다 실행시간도 꽤 큰 차이가 납니다. 그러니 저정도는 거의 시간차이가 없다~ 동일한 시간복잡도다! 라고 생각하셔도 돼요.

굳이 따져보면, 재귀를 하면 시간이 더 오래걸릴 수 도 있고, 그러다보면 상수값의 차이때문에 재귀가 시간이 더 걸리기도 하는데, 어떤 상황에서는 재귀가 더 빠를 수 도 있기 때문에 testcase값마다 엎치락 뒤치락 할 수 도 있을 것 같아요.

결론: 저정도 시간차이면 누가 빠르다고 논하기는 쉽지 않다.

질문자

아아 그렇군요! 어쩐지 같은 문제를 여러번 풀어서 제출했을 때 런타임시간이 가지각색이라 왜 코드가 같은데 시간이 다르지? 라는 의문을 가졌는데 검색해보니 서버 환경에 따라 시간이 달라질 수도 있다고 하네요! 감사합니다 :)