ahrist123456   1년 전

설명에 O(nlogn) 이라는 단어가 있는데 그건 의미가 뭔가요?

not_strober   1년 전

O(N log N)은 알고리즘(또는 프로그램)의 시간 복잡도를 빅오(Big-O) 표기법으로 나타냈을 때 N log N이라는 말이며 입력 N에 대해 알고리즘의 실행에 N * log N에 비례하는 시간이 걸린다는 의미입니다. 대중적으로 쓰이는 많은 정렬 알고리즘의 시간 복잡도는 O(N log N)입니다. 빅오 표기법과 시간 복잡도에 대해 알아보시는 걸 추천드립니다.

여담으로, 이 문제는 Counting sort로 푸는 문제이므로 시간 복잡도가 O(N log N)이 아닌 O(N + K)입니다. K는 입력의 상한으로, 이 문제에서는 10,000입니다.

댓글을 작성하려면 로그인해야 합니다.