programmer life guidance 101

> 알고리즘의 분석 알고리즘의 자원(resource) 사용량을 분석 자원이란 실행시간, 메모리, 저장장치, 통신 등 여기서는 실행시간의 분석에 대해서 다룬다. 시간복잡도 실행시간은 실행환경에 따라 달라짐 하드웨어, 운영체제, 언어, 컴파일러 등 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 데이터의 크기가 같더라고 실제 데이터에 따라서 달라짐 최악의 경우 시간복잡도(worst-case analysis) 평균 시간복잡도(average-case analysis) 점근적(Asymptotic) 분석 점근적 표기법을 사용 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법 Θ-표기, Ο-표기 등을 사용..

> Locality의 관점에서 Quick sort가 Merge sort보다 빠른이유 Quick sort와 Merge sort는 nlogn의 시간복잡도를 가지는 대표적인 정렬 방법이다. 일반적으로 Quick sort가 Merge sort보다 크다. 그 이유는 Locality와 관련이 있다. Locality의 개념을 알아보고 왜 Quick sort가 더 빠른지 알아보도록 하자. Locality 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. 메모리 내의 정보를 균일하게 엑세스 하는게 아닌, 짧은 시간내에 특정 부분을 집중적으로 참조하는 특성이다. void f() { //간단한 작업을 수행 } void g() { int arr[1000]..