인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

Inflearn Community Q&A

이성현's profile image
이성현

asked

[MMORPG Game Development Series with C# and Unity] Part 2: Data Structures and Algorithms

A* Implementation Part 1

Array.Sort()와 PriorityQueue의 차이

Written on

·

456

0

제일 좋은 후보를 찾기해서는 PriorityQueue말고 배열의 내림차순을 할 수 있는 Array.Sort()도 사용 가능 할것 같은데 두 함수 사이의 성능차이가 커서 사용을 하시지 않은 것 인가요?

C#

Answer 1

3

rookiss님의 프로필 이미지
rookiss
Instructor

PriorityQueue는 성능 O(logN)이고,
그냥 배열에 있는 애 중 하나를 쭉 스캔하면서 제일 좋은 후보를 찾으면 O(N)이고
Array.Sort는 O(NlogN)으로 제일 느립니다.

가장 우수한 후보 1개만을 뽑으면 되는데,
데이터 N개를 모두 정렬하는 수고를 굳이 할 필요가 없겠죠.
logN >> N >> NlogN 셋 차이는 완전 넘사벽으로 어마무시합니다.
데이터가 1억개라도 logN은 몇십번의 연산으로 끝내지만
N이나 NlogN은 연산 몇억번이 필요합니다.

이성현's profile image
이성현

asked

Ask a question