알고리즘 실용화

가까운 예로 보는 이론 · 연구의 실전 투입

「대규모 서비스를 지탱하는 기술」 Chapter 07

---

데이터 구조

• 배열, 트리구조, 힙 등
• 알고리즘에서 자주 사용하는 조작에 맞춰 선택

 

알고리즘 Order 표기의 상수항

• 해당 알고리즘을 구현하는 중 입력 크기에는 의존하지 않지만 실행하지 않으면 안 되는 처리의 일종
• e.g. 함수호출이나 함수로부터 값을 반환하기 위한 처리, 일차변수 확보, if문 분기

 

Order 표기 유의점

• 계산량 O(n^2)인 알고리즘을 나름대로 노력해서 상수항을 줄이는 연구를 하더라도 이를 대체해서 O(n log n)인 알고리즘이 있다면 후자를 사용하는 편이 개선효과가 더 클 것
• → ‘측정이 중요’하다는 얘기로, 지금 대상으로 하는 프로그램에 무엇이 문제인가를 정확하게 아는 것이 중요
• 알고리즘을 교체해서 개선해야 할 것인지, 상수항을 줄여서 개선해야 할 것인지, 물리적으로 리소스가 부족하므로 하드웨어를 교환해서 성능을 개선해야 할 것인지 등