[자료구조]탐색알고리즘, 시간복잡도

1.

순차탐색 알고리즘, 시간복잡도

 

연산횟수의 함수 T(n)을 구해보자.

이 알고리즘에서 사용된 연산자는 <, ++, == 세 개. 그럼 이 중에 어떤 연산자를 기준으로 세어야할까?

탐색 알고리즘에서의 핵심은 동등비교를 하는 비교연산이다.

비교연산의 수행횟수가 줄어들면 <, ++연산의 수행횟수도 줄어들고,

비교연산의 수행횟수가 늘어나면 <,++ 연산의 수행횟수도 늘어나기 때문이다.

 

∴ == 연사의 횟수를 대상으로 시간 복잡도를 분석하면 된다.

 

 

 

2.

이진 탐색 알고리즘 구현

 

while(first <= last){

//이진 탐색 알고리즘의 진행

}

 

first<=last가 반복조건.

first = last라면 탐색의 대상이 아직 하나 남아있음을 뜻하기 때문에, 이진탐색은

first<last, first==last인 상황에서도 계속되어야 한다.

 

 

 

3.

빅-오 표기법의 성능(수행시간 연산횟수)의 비교

 

 

 

 

4.

빅-오의 수학적 정의

 

두 개의 함수  f(n)과 g(n)이 주어졌을 때, 모든 n≥k에 대하여 f(n)≤C*g(n)을 만족하는

두 개의 상수 C와 K가 존재하면, f(n)의 빅-오는 O(g(n))이다.

 

 

의 빅-오는 이다.

 

이 아무리 연산횟수의 증가율이 커도

증가율의 패턴이 을 넘지 못한다.

 

여기서 C는 5이고 K는 n^2의 증가율패턴이 연산횟수의 증가율을 넘는 때의 n.

(연산횟수의 증가율이 아무리커도 증가율의 패턴을 못넘는 증거의 K)

 

[4_ex]

 

 

 

5.