자료구조 최종정리 : (1) 빅오표기관련..

1. 연산의 빈도를 찾거나..(일일이 n에 따른 더하기 대입(n이 직접영향받는것이 아니라 n에 영향을 받아 계산되는것 포함)..등등 계산이 몇번되는가..)

예)

test(n)

{

i=0; 최초 1번

sum=0; 최초 2번

for(;i<=n;i++)

sum+=i;

return sum;

}

최초 1,2번 이후에 for문에서는..연산이..

n의 영향을 받아 총..

i<=n 1번, i++ 2번, sum+=i 3번 일어나므로..

3n + 2이다..

즉 n임..

 

2. 대표연산을 찾고...이 대표연산이 n에 따른 횟수를..찾는다.

예)

while(first<=last)

{   

mid=(first+last)/2;

if(target==ar[mid])

{

return mid;

}

else

{

}

}

라면..여기서 대표하는 연산은 ==이것..왜냐면..==이 빠르면 빠를 수록 연산은 빨리 끝나니까..

1. 처음에 데이터의 수가 n개일때의 탐색과정에서 1회의 비교연산 진행

2. 데이터의 수를 반으로 줄여서 그 수가 n/2일 떄의 탐색과정에서 1회 비교연산 진행

3. 데이터의 수를 반으로 줄여서 그 수가 n/4일 때의 탐색과정에서 1회 비교연산 진행

.

.

n이 얼마인지 결정되지 않았으니 이 사이에 도대체 몇 번의 비교연산이 진행되는지 알 수가 없다..!

끝. 데이터의 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회의 비교연산 진행(마지막 연산이다.)

만약 n이 8이라면..

8이 1이 되기까지 2로 나누는 과정을 총 3회 거쳐야한다..즉..정리하면

8이 1이 되기까지 2로 나눈 횟수 3회 따라서 비교연산 3회 진행

데이터가 1개 남았을때 이때 마지막으로 비교연산 1회 진행

 

n이 1이 되기까지 2로 나눈 횟수 k회 따라서 비교연산 k회 진행

데이터가 1개 남았을때 이때 마지막으로 비교연산 1회 진행

n=k + 1

근데 k를 구해야한다.n이 1이 되기까지 2로 나눈 횟수가 k 이므로..n과 k에 관한식은

n * (1/2)^k = 1 이다..(2로 몇번 나누어야 1이 되는가에 대한 답을 주는 수식) 이걸 정리하면

= n* 2^-k=1

= n=2^k

(a^-n은 1/a^n 으로 표현가능하다..지수법칙)

* n이 왜 2^k냐면..위에 = n* 2^-k=1, 1이 잖아..그럼 지수법칙에 의해 n^0이 1이 되어야 해..지수 법칙에서 또 곱하기는 지수끼리 더한단말이야..그럼..

2^-k와 2^k 가..곱해지면 2^(k+-k) = 2^0이 잖아..그래서 1이지..

 

근데 우리가 여기서 구하는것은 k값이잖아.. n= 2^k 그럼 이걸..로그를 취해서..

log2n=log2 2^k = log2n = klog2 2 = log2n=k

로그 규칙은 아래에..

 로그의 정의

 

 로그의 기본성질

밑의 변환공식

n=log2n

 

1. 가장 큰 영향력(항)을 주는 것을(N을) 찾고..

2. 계수를 생략하면 된다.

3n + 3의 경우..

1 -> 3n

2 -> n

최종 n..

 

 

비교는

1 > logn >n >nlogn >n^2 >n^3 >2^n >n!

이런 순서다..

 

해당내용은 윤성우의 열혈 자료구조와 열혈강의 자료구조를 참고했습니다.