leetcode 의 analyze complexity 를 믿어도 될까요?

[wogha95]

Construct Binary Tree From Preorder And Inorder Traversal 문제를 풀고 complexity 계산 도중에 의문점이 생겼습니다.

제 풀이의 시간복잡도는 preorder 순회 O(N) 에 findIndex 순회 O(N) 이 중첩되어 있으니 O(N^2)로 생각했습니다. 그러나 leetcode analyze 에서는 시간복잡도를 O(N)으로 알려줍니다. 혹시 제가 시간복잡도 계산을 잘못한 것일까요?

[SamTheKorean]

해당 문제를 아직 보진 않았지만, 일반적으로 분석이 맞지만 틀린 경우나 매우 창의적으로 분석하는 경우도 종종 봐서 개인적으로 신뢰하지는 않고 있습니다!

[DaleSeo]

저도 LeetCode의 복잡도 분석 기능을 써봤는데 틀린 적이 너무 많아서 신뢰하고 있지 않습니다. 직접 분석하신 결과 O(n^2)이 맞다고 생각합니다 👍

[TonyKim9401]

전 TC, SC 모두 제가 계산 후에 검토용으로 코드 그대로 입력해서 GPT로 계산 해달라고 하고 비교해봐요 :)