hotehrud   4달 전

이진트리를 만들 때 아래 소스가 정석 아닌가요...?

어떻게 풀어야하는거죠?

삽입하면서 카운트를 세면 안되는건가요

flflds0811   4달 전

이진탐색트리의 삽입,삭제,탐색 시간복잡도는 O(h)입니다.

O(logn)<=O(h)<=O(n)이므로  O(n)으로 볼 수 있습니다.

하나의 입력마다 삽입을하며 카운트를 한다면, 알고리즘의 시간복잡도는 

최악의 경우 O(1)+O(2)+...O(n) = O(n^2)

n이 30만까지 들어온다고 하였으므로 30만 제곱의 시간이 걸리게 되므로

제한시간 1초에는 불가능합니다.

이진탐색트리에서 삽입되는 특징을 찾아서 O(n^2)보다 빠른 시간복잡도의

알고리즘으로 문제를 해결해야합니다.

댓글을 작성하려면 로그인해야 합니다.