시간복잡도 질문

23.11.05 16:34 작성 조회수 315

3중 for문으로 카드를 뽑으면 간단하다는 건 알고있었지만,

이러면 시간복잡도가 O(n^3) 이 되면서 시간초과가 나면서 안될 것 같다고 생각했습니다... 보통 n이 몇까지 가면 시간초과가 발생하나요? 이걸 제대로 몰라서 이중for문도 조심스럽습니다.

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

5. K번째 큰 수(영상 후반 TreeSet 추가설명)

강의실 바로가기

답변 1

답변을 작성해보세요.

김태원

2023.11.07

안녕하세요^^

보통 코딩테스트에서 n제한이 100,000만 이상이면 이 문제는 효율성 테스트를 하는 문제라고 생각해야 합니다.

n제한이 10만 이상이면 O(n^2)으로는 시간초과가 나고 보통 O(n) 또는 O(nlogn)으로 짜야 효율성 테스트를 통과할 수 있습니다.

구준형

2023.11.07

감사합니다!