naong606   8년 전

안녕하세요!

분할정복으로 2574번 구현해서 ACC를 받았는데요

Worst case에선 O(n^2) 시간복잡도가 나오는 것 같은데 ACC가 나와서 의아했습니다


예를 들어,

40000 40000 

30000

1 1

1 2

2 2

2 3

3 3

3 4 ....

이런 식으로 진행되는 testcase에서 제 코드는 O(n^2) 시간복잡도를 갖는데,

n <= 30000이면 O(n^2)가 1초 안에 작동된다고 생각해도 무방한가요?

아니면 실제 testcase엔 이런 worst case는 반영이 안 된건가요? 

감사합니다!


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