Think Data Structures (2) -초보개발자-

- 프로파일링 (profiling : 자료 수집)

어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법.

둘 다 시도해 보고 각각 얼마나 걸리는지 알아보는 것.

 

문제점)

1. 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 한다.

2. 결과는 사용하는 컴퓨터의 성능에 의존한다. (컴퓨터마다 결과가 다름)

3. 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 한다. ----- (이해되지 않음)

 

---- > '알고리즘 분석'을 사용하여 문제점 해결 가능

 

[ 알고리즘 분석은 그것을 구현하지 않고도 알고리즘을 비교할 수 있게 함 ]   But ;; 몇 가지 가정을 해야 한다.

 

1. 컴퓨터 하드웨어의 세부사항 다루지 않기 위해

   알고리즘 이루는 더하기, 곱하기, 숫자 비교 등의 기본 연산을 식별한다.

   그리고 각 알고리즘에 필요한 연산 수 센다.

2. 좋은 선택은 기대하는 입력 데이터에 대한 평균 성능을 분석하는 것이다.

   이것이 가능하지 않을 때는 최악의 시나리오를 분석하기도 한다.

3. 문제마다 다른 알고리즘이 더 좋을 수 있다는 것을 알아야 한다.

   이때, 보통 큰 문제에 초점을 맞춘다.

 

 

------------------------------------------------------------------------------------------------

실행 시간에 따라 알고리즘은 몇 가지 범주로 나뉜다.

 

1. 상수 시간

실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간을 따른다고 한다.

 

2. 선형

실행시간이 입력의 크기에 비례하면 알고리즘은 선형이라 한다.

 

3. 이차

실행시간이 n^에 비례하면 알고리즘은 이차라고 한다.

 

-----------------------------------------------------------------------------

 

빅오 표기법

모든 상수 시간 알고리즘은 O(1)이라는 집합에 속한다.

모든 선형 알고리즘은 O(n)에 속하며 

모든 이차 알고리즘은 O(n^)에 속한다.

 

이렇게 알고리즘을 분류하는 방식을 '빅오 표기법'이라 한다.