• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

시간복잡도 기준 질문

23.02.13 00:03 작성 조회수 203

0

전 강의(수의 합)에서는 시간복잡도 때문에 for문 한번만 작성해야하고 어느문제는 그냥풀어도 되는건지 그 기준이 궁금합니다.

course-thumbnail

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

6. 격자판 최대합

강의실 바로가기

답변 1

답변을 작성해보세요.

1

김태원님의 프로필

김태원

지식공유자

2023.02.14

안녕하세요^^

대략적으로 n(입력의 크기)제한이 100,000 이상이면 시간복잡도 O(n^2)으로 했다가는 시간초과 날거라는 출제자의 의도라 생각하시면 좋겠습니다. n제한이 100,000이상이면 O(n) 또는 O(nlogn)으로 하라는 의도가 있다고 봐야 합니다. 물론 무조건적인 것은 아닙니다. 아닐 수 도 있지만 대략 그렇다입니다.

이 글과 비슷한 Q&A