[질문] 스플레이 트리 궁금한거 있음

[익명(61.40)]

최악의 경우 시간복잡도가 O(N) 이던데 저격하면 터지는거 아님?

[대학원오지마세요(publfl)]

할수있다면 말이지

[익명(61.40)]

너무 복잡해서 못하는거임?

[익명(61.39)]

최악은 O(N)인데 Q번의 쿼리가 있다고 하면 Q번 쿼리가 있다고 하면 Q번의 쿼리 전체 시간 복잡도가 O(QlogQ)임

[스누피(211.36)]

amortized가 뭔지 검색 ㄱㄱ

[익명(211.57)]

평균내면 결국 시간복잡도가 크지 않음이 증명되어 있음

[MetaFibonacci(equivalence)]