for 문에 sort 함수 를 사용하면

코딩테스트 [ ALL IN ONE ]

🎁시간복잡도 총정리🎁

작성

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요 선생님. 수업 잘 듣고 있습니다.

sort 함수 관련해서요. sort 함수가 nlog(n)의 시간 복잡도를 가지면 n번 반복하는 for문 아래에 sort 함수가 들어가면 n^2log(n)이 되는게 맞을까요?

python 코딩-테스트 알고리즘

답변 2

[노씨데브 코치] 구운햄

지식공유자

안녕하세요, sch629님

네, 원칙적으로 맞습니다.

sort()는 평균적으로 O(n log n)의 시간 복잡도를 가지기 때문에, 그걸 n번 반복하는 for문 안에서 매번 실행한다면 전체적으로 O(n² log n)이 됩니다.

다만, 실제로는 매번 정렬해야 하는 상황인지, 정렬하는 데이터의 크기가 일정한지에 따라 실제 실행 시간은 달라질 수 있습니다.

감사합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. sch629님.

질문해주신 내용은 for 문 내부에서 sort 함수를 사용했을 때의 시간 복잡도에 관한 것이네요. 관련된 내용을 더 잘 이해하기 위해 가능한 예시와 설명을 드리겠습니다.

for문 및 sort 함수의 시간 복잡도: 기본적으로 sort 함수의 시간 복잡도는 O(n log n)입니다. 만약 sort 함수를 for문 내부에서 돌린다면, 각 반복문에서 배열을 정렬하게 되어 전체적으로 O(n * n log n) 즉, O(n^2 log n)의 시간 복잡도가 될 수 있습니다.
구체적인 이해의 중요성: 일반적으로 for문과 sort 함수의 결합으로 인해 높은 시간 복잡도가 발생하는 경우, 최적화를 고려해야 합니다. 예를 들어, 매번 정렬을 하지 않도록 프로그램의 논리를 수정하거나, 필요에 따라 다른 자료구조 혹은 알고리즘을 사용해 볼 수 있습니다.

이와 유사한 질문은 다음 게시물에서 다뤄진 바 있습니다:
- “Sorting algorithm”: 강사님이 제공한 답변에서 파이썬의 내장 sort 함수와 관련된 효율성에 대해 논의하고 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

for 문에 sort 함수 를 사용하면