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

안녕하세요 minsu님
sort함수의 nlogn이 맞습니다.
4분 30초대의 내용을 보시면 정렬이 되어있는 숫자중에 하나를 찾을때는 log n입니다.

그 후 8분대에 설명하는 n log n은 정렬되지 않은 숫자 중 하나를 찾을 때는 전부 하나하나 비교를 해야하기 때문에 n이 곱해지는 겁니다.

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

강의 중에 나오는 nlogn 복잡도에 대한 설명에 대해 혼란스러우실 수 있을 것 같습니다. 프로그래밍 알고리즘에서 nlogn은 주로 “정렬 알고리즘”의 시간 복잡도를 나타내며, 특히 C++의 STL에서 제공하는 sort 함수의 시간 복잡도가 nlogn인 경우가 많습니다.

1. nlogn 이해하기: 이 복잡도는 데이터의 크기가 n일 때, 데이터 정렬에 걸리는 시간을 설명합니다. n은 데이터 항목의 수를 나타내고, logn은 효율적인 정렬을 위한 기준 사이의 비교 횟수를 줄이기 위한 로그 함수를 나타냅니다. 즉, 데이터가 커질수록 비교 및 정렬해야 할 작업이 늘어나지만, log 함수를 통해 효율적으로 이 작업의 수를 줄이는 것입니다.

2. STL의 sort 함수: C++에서 사용하는 STL의 sort 함수는 대표적인 nlogn 복잡도를 가지는 알고리즘입니다. 이는 대부분의 경우 퀵 정렬(Quick Sort) 또는 다른 효율적인 알고리즘을 기반으로 하며, 일반적으로 평균적으로 nlogn의 시간에 작동합니다.

이러한 정렬 알고리즘에 대한 더욱 자세한 정보를 확인하시려면 아래의 게시물을 참고하실 수 있습니다:

• STL sort 함수의 시간 복잡도: STL sort를 포함한 다양한 알고리즘의 복잡도 및 작동 방식에 대한 설명이 포함되어 있습니다.
  

강의의 맥락을 이해하는 데 도움이 되었기를 바랍니다. 추가적인 설명이 필요하다면 강의 내 질문 게시판에 문의하셔서 강사님이나 다른 수강생들의 의견을 얻으시는 것도 좋은 방법입니다.

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