levelorder 방식과 postorder 방식에서의 시간복잡도에 관해 질문이 있습니다.
강사님께서는 어짜피 둘다 모든 노드를 순회해야 하기 때문에 최악의 경우에도 시간복잡도가 O(N)이라고 하셨습니다. 그런데 아래와 같이 leetcode에 제출한 결과 런타임이 다르게 나와서 의문이 들었습니다.
위가 postorder고, 아래가 levelorder인데 왜 levelorder가 더 빠른건가요?? 아니면 시간복잡도는 대략적으로 계산한 결과이기 때문에 실제 런타임을 돌린 결과에서는 상수값의 차이가 나서 저런 결과가 나온건가요??
답변 1
1
안녕하세요 앰비션님!
저정도 시간차이면 거의 시간차이가 없다고 보셔도 됩니다.
동일한 코드를 몇번 실행해보면 그때마다 실행시간도 꽤 큰 차이가 납니다. 그러니 저정도는 거의 시간차이가 없다~ 동일한 시간복잡도다! 라고 생각하셔도 돼요.
굳이 따져보면, 재귀를 하면 시간이 더 오래걸릴 수 도 있고, 그러다보면 상수값의 차이때문에 재귀가 시간이 더 걸리기도 하는데, 어떤 상황에서는 재귀가 더 빠를 수 도 있기 때문에 testcase값마다 엎치락 뒤치락 할 수 도 있을 것 같아요.
결론: 저정도 시간차이면 누가 빠르다고 논하기는 쉽지 않다.
0
아아 그렇군요! 어쩐지 같은 문제를 여러번 풀어서 제출했을 때 런타임시간이 가지각색이라 왜 코드가 같은데 시간이 다르지? 라는 의문을 가졌는데 검색해보니 서버 환경에 따라 시간이 달라질 수도 있다고 하네요! 감사합니다 :)
노션 공유 링크
0
84
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
74
2
최신 강의와 비교
0
79
2
Min Cost Climbing stairs 질문
0
74
2
노션 공유 부탁드립니다!
1
85
2
for 문에 sort 함수 를 사용하면
1
86
2
노션 공유 부탁드립니다.
0
101
2
디스코드가 올바르지 않다고 뜹니다..!
0
104
1
그래프
0
96
2
노션 공유
1
121
2
시간복잡도 질문
2
122
3
11강 질문
1
75
2
노션 공유 부탁드립니다
0
82
2
linkedList - BrowserHistory 코드 질문
0
72
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
165
1
라이브러리 사용
1
134
2
문제 교재는 따로 없는 거 맞나요?
1
200
2
LCA 관련해서 질문이 있습니다.
1
116
2
[Unique Paths] 완전탐색 / DP (후반부)
0
104
1
dp 계단오르기최소비용질문입니다.
0
106
1
Dynamic Array 의 size 정보가 저장되는 곳
2
159
2
노션공유가 안된듯 합니다
1
161
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
119
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
199
1