인프런 커뮤니티 질문&답변
작성한 질문수
시간 복잡도
작성
·
242
0
선생님 안녕하세요
아이디어를 코드로 구현하기 전에 시간복잡도를 생각해 시간초과가 발생할지 안할지 생각해보고 시간초과가 안날 것 같을 때 그 아이디어를 코드로 구현해야 시험에서 시간낭비가 없을 것 같은데 그 기준을 어떻게 잡아야 하나요? 왜냐면 지금 이 문제는 시간복잡도가 n제곱임에도 시간초과가 안나지만 어떤 문제는 시간초과가 나서 질문드립니다
답변 1
0
김태원
지식공유자
안녕하세요^^
문제에서 제시하는 입력제한(n크기) 즉 입력데이터의 크기인 N제한을 보고 보통판단합니다.
판단의 기준은 n의 크기에 때라 N^2가 통할지 아니면 NlogN으로 해야 할 지 아니면 O(N)으로 해야 할 지 판단하는 것은 많은 문제를 풀어본 경험에서 나온다고 봅니다. 여기서 수치적으로 N이 100,000이상이면 N^2안통한다 이렇게 단정지을수는 없지만, 대충 이렇게 자기만의 기준을 경험에 의해서 가지고 있습니다.