[자료구조] 2강 1장 기본 개념 - 4절 순환 알고리즘

1장 기본 개념 - 4절 순환 알고리즘

 

* 순환알고리즘

정의하려는 개념자체를 정의 속에 포함하려 사용하는 방법

직접 순환 : 함수가 직접 자신을 호출

간접 순환 : 다른 제3의 함수를 호출하고 그 함수가 다시 자신을 호출

어떤 복잡한 문제를 직접 간단하게 풀 수 있는 작은 문제로 분할하여 해결하려는 방법인 분할 정복의 특성을 가진 문제에 적합

 

ex) factorial

 

Procedure factorial(n)

if n<= 0 then return 1

return (n * call factorial(n-1));

end factorial

 

위 예시의 경우 factorial 안에 factorial을 넣음으로서 순환 알고리즘을 형성하였다.

 

* 순환알고리즘의 또 다른 경우 : 이원 탐색 알고리즘

특정한 원소를 찾기 위하여 주어진 리스트를 중간값을 기준으로 2개의 서브 리스트로 분할 -> 중간값과 찾고자 하는 원소를 비교하여 찾고자 하는 값이 큰지 작은지를 판별하여 해당 서브 리스트에 대하여 똑같은 알고리즘을 다시 적용 -> 특정한 원소를 찾거나 모든 리스트를 모두 검색할때까지 반복

 

* 성능 분석

프로그램을 실행하는데 필요한 시간과 공간의 추정치를 분석하는 방법 (보통은 이방법을 사용)

컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간을 측정하는 방법

성능분석을 위해서는 공간적인 효율성과 시간적인 효율성이라는 복잡도로 평가

 

* 공간 복잡도 (Space Complexity)

프로그램을 실행시켜 완료하는데 까지 소요되는 총 저장 공간

공간 복잡도 = 고정 공간 + 가변 공간

 

* 시간 복잡도 (Time Complexity)

프로그램을 실행시켜 완료하는데 까지 걸리는 시간

시간 복잡도 = 컴파일 시간 + 실행 시간

컴파일 시간은 프로그램마다 거의 고정적인 시간이 소요

실행 시간은 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행 시간보다는 명령문의 실행 빈도수에 따라 계산 (명령문이 몇 번 실행되었느냐를 확인한다 -> 적을수록 빠르다)

 

ex) fibonacci

 

fibonacci(n)

if (n<0) then

stop;

if (n<=1) then

return n;

f1 ← 0;

f2 ← 1;

for (i←2; i≤n; i←i+1) do{

fn←f1+f2

f1←f2;

f2←fn;

}

return fn;

end

 

O(n) = 전체 실행 시간 = 4n+2

 

<연산 시간 표기법>

 

* Big-Oh(O)

f와 g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a, b가 존재하고 모든 n>=b 에 대해 f(n)<=a*g(n) 이면 f(n)=O(g(n)) 으로 표기

 

ex)

f(n) = 3n+2 이면 a=4, b=2 가 존재하고 f(n)=O(n) 이다.

 

f(n) = 1000 + 100n-6 이면 a=1001, b=100 dl 존재하고 f(n) = O( ) 이다.

 

* 연산 시간의 크기 순서

상수시간 : O(1)

로그시간 : O( )

선형시간 : O(n)

n로그시간 : O(n )

평방시간 : O( )

입방시간 : O( )

지수시간 : O( )

계승시간 : O(n!)

위에서 아래로 시간 복잡도가 비효율적

 

* Big-Omega( )

f와 g가 양의 정수를 갖는 함수일 때 두양의 상수 a,b가 존재하고 모든 n>= a*g(n) 이면 f(n)= (g(n)) 으로 표기

ex)

f(n)=3n+2 이면 a=3 b=1 가 존재하고 f(n)= (n)이다

f(n)=1000 +100n-6 이면 a=1000, b=1 이 존재하고 f(n)= ( ) 이다.

 

* Big-Oh(O) 와 Big-Omega( ) 의 차이점

전자는 상한 후자는 하한

 

* Big-Theta( ) - 상한과 하한을 모두 표시

f와 g가 양의 정수를 갖는 함수일 때 세 양의 상수 a,b,c가 존재하고 모든 n>=c에 대해 a*g(n)<=f(n)<=b*g(n) 이면 f(n)= (g(n)) 으로 표기

ex)

f(n)=3n+2 이면 a=3 b=4 c=2 가 존재하고 f(n)= (n) 이다.

f(n)=1000 +100n-6이면 a=1000 b=10001 c=100 이 존재하고 f(n) ( ) 이다.

 

* 실용적인 복잡도

복잡도 함수는 같은 작업을 수행하는 두 개의 프로그램 P와 Q를 비교하는데 유용

프로그램 P가 복잡도 (n)

프로그램 Q는 복잡도 ( )

→ 프로그램 P가 프로그램 Q 보다 충분히 큰 n 에 대해 더 빠르다.

 

-증가 추세가 완만한 것이 효율적인 프로그램이다.

표시가 안되는 부분은 수식입니다.