jiggyjiggy

Q.정렬 알고리듬은 실제 성능은 시간 복잡도 외에도 데이터의 정렬 상태, 실행 환경(하드웨어, OS) 등 다른 요인과도 관계가 있는 것 같다. 특히, 캐시 활용도에 대한 내용이 많이 언급되었는데, 캐시 활용에 유리한 알고리듬의 특성은 무엇인지 궁금하다.A.시간 복잡도는 가이드라인일 뿐이고 실무에서는 그보다는 다른 요인들이 더 큰 영향을 미친다. (아주 느린 시간 복잡도가 아니라는 가정)캐시 활용에 유리한 알고리즘의 특성은 크게 두 가지이다.지역성(locality): 캐시는 CPU가 자주 접근하는 데이터를 압도적으로 빠르게 가져올 수 있도록 설계된 메모리 계층이다. 캐시는 데이터를 블록 단위로 가져오기 때문에, 인접한 데이터에 연속적으로 접근할 때 캐시 히트율이 높아진다. 따라서 캐시 활용에 유리한 알고리..