알고리즘 내용정리- 1

• 알고리즘 : 문제 해결위한 단계적 절차, a set of unambiguos instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data.
• 문제의 요구조건 입력과 출력으로 명시할 수 있고 알고리즘은 입력으로부터 출력을 만드는 과정

• 입력 : 문제의 사례, 파라미터 에 특정 값을 지정한 것, 출력 : 사례에 대한 해답, 주어진 사례에 관한 질문에 대한 답 , 파라미터: 문제에서 특정값이 주어지지 않은 변수

• 최초의 알고리즘 : BC300년경 유클리드 최대공약수 알고리즘

• 유클리드 최대공약수 알고리즘 : 2개의 자연수의 최대공약수는 큰수에서 작은 수를 뺀 수와 작은 수의 최대공약수와 같다. ex) 18,6 -> 12,6 -> 6 -> 최대 공약수는 6 ex) 49,21 -> 28,21 -> 7 ->최대 공약수는 7

• 알고리즘의 표기 : 의사코드( Pseudo-code)를 통해 - 직접 실행할 수 있는 프로그래밍 언어X, 거의 실제코드에 가깝게 표현한 언어. 앞으로의 코드표기는 모두 의사코드

• 알고리즘의 특성 : 정확성 (주어진 입력에 대한 올바를 해를 준다), 수행성 (각 단계는 컴퓨터에서 수행 가능하다), 유한성 (일정 시간내에 종료된다), 효율성 (효율적일수록 가치가 높다)

• 효율성의 척도 : 시간복잡도 (time complexiy, 입력크기에 따라 단위연산이 몇 번 수행되는지), 공간복잡도 (space complexity, )

• 단위연산(basic operation): 비교 (comparision) 와 지정(assignment)

• 입력크기(input size) :배열의 크기, 리스트 길이, 행렬에서 행과열의 크기, 트리에서 노트와 연결선의 수

• Comlexity : log n < n < nlog n < n^2 < n^3 < 2^n < n! (n이 충분히 클 때)

• 알고리즘의 분류 : 문제 해결방식에 따른 분류 – 분할정복（divide and conquer) 그리디 (Greedy) 동적 계획(Dynamic Programming) 등

• 예) 최대 숫자 찾기의 경우 하나씩 차례로 (주어진 순서대로) 읽으며 찾는 방법 : 순차탐색

• 예) 임의의 숫자 찾기 – 위처럼 순차탐색(Sequential Search)또는 숫자들이 정렬되어있을 경우, 숫자들을 반으로 나눠 비교, 없으면 나눠진 반에서 찾는 것을 반복해 찾는 이진탐색(Binary Search)방법

• 1) 순차탐색(Sequential Search)
  void seqsearch( int n, const keytype S[], keytype x, index &location //입력,입력,입력, 출력 ) {
  location = 1;
  while( location <=n && S[location] != x ) location ++;
  if ( location > n ) location = 0;｝ //S를 모두 검사했으나 없다 .
  순차검색 알고리즘의 경우 최고의 경우 1번 (첫 번째에 찾음) 최악의 경우 n번 (맨 마지막에 찾음)의 검색을 시행행함.

• 2) 이분검색 알고리즘(Binary Search)
  void binsearch(int n, constkeytype S[], keytype x, index& location //입력,입력,입력, 출력) {
  index low, high, mid;
  low=1; high = n; location=0;
  while( low <= high && location == 0) {
  mid = (low+high)/2
  if (x == S[mid]) { location = mid; } //가운데 값에서 찾는 수를 찾음
  else if (x < S[mid]) { high = mid –1; } //찾는 수가 가운데 값보다 작음
  else { low = mid + 1; } // 찾는 수가 가운데 값보다 큼
  }
  }
  위의 이분검색 알고리즘은 while수행할 때마다 검색 대상(S배열)의 크기가 1/2만큼 줄어든다.
  최고의 경우 1번 최악의 경우 1+log n 번 (여기서 log 는 이진로그, base=2 )

• 알고리즘 수행시간의 헷갈리는 예시
  ex1) function1 (A[] , n) {
  sum <-0;
  for i <- 1 to n
  for j <- 1 to n {
  k <- A[1 .. n ]에서 임의로 [n/2]개 뽑을 때 이 중 최대 값;
  sum < -sum +k;
  }
  return sum;
  }
  이런 알고리즘의 경우 소요시간은 n^3이다.
  내가 생각한 대략적인 이유는 n C n/2 의 경우 n=2k로 두면 k=n/2이고
  n C n/2 = 2k C k = (2k) (2k-1) (2k-2) (k+1) / k(k-1)(k-2)1 분모 분자 모두 k개씩 있으므로 위의 식은 > k^k / k^(k-1)= k 이므로 k=n/2 만큼 소요된다. n/2만큼 소요되는 연산을 j for문에서 n만큼, i for문에서 n만큼 하므로 n n n/2 -> n^3에 비례하는 시간이 소요

• n번째 피보니치 수 구하기 예제

• 1) 재귀적(recursive)방법
  int fib (int n) {
  if (n <= 1)　｛
  return n; }
  else { return fib (n-1) + fib (n-2) ;}
  } 이경우 fib()를 구하기 위해 중복 계산하는 것이 많음

T(n)을 fib(n)을 계산하기 위해 fib함수를 호출하는 횟수라고 할 때,
T(0) =1 , T(1) =1 , T(n) = T(n-1) + T(n-2)+1 (n ≥2)
> 2 T(n-2) > 2^2 T(n-4) > ... >2^n T(n-2n)
이 말은 2^n/2 T(n –n) 이고
T(n-n) = T(0)=1이므로 2^n/2 즉, n ≥2인 모든 n에 대해 T(n) > 2 ^(n/2) 이다.

• 2)번 반복적 방법으로 피보나치 수 구하기
  int fib2 (int n) {
  index i;
  int f[0 .. n];
  f[0] = 0;
  if (n >0){
  f[1] =1;
  for (i=2; i <=n; i++) {
  f[i] = f[i-1] + f[i-2] ; //n짜리 배열에 피보나치 수열 값 저장
  } return f[n];
  }
  이 경우 반복 알고리즘에서 계산하는 항목의 총 개수 T(n) = n+1, 즉 f[0]부터 f[n]까지 중복계산 없어 수행속도가 더 빠르다.

• 분석방법의 종류 : 최선의 경우 (Best-case analysis, 수행 횟수가 최소). 최악의 경우(Worst-case analysis, 수행 횟수가 최대), 평균의 경우(Average-case analysis, 모든 입력에 대해 단위연산 수행되는 기대치)

• 예1) 배열의 원소 덧셈의 경우 for(i=1; i<=n; i++) rs = rs + S[i];
  단위연산 : 덧셈 – i++와 rs덧셈 -> T(n)=2n 과
  지정문 – for 루프의 첨자 지정문과 rs지정 총 횟수는 1+1+2n, T(n)=2n+2

• 예2) 교환정렬, 문제: 비내림차 순으로 n개의 키를 정렬
  void exchagesort (int n, keytype S[]) {
  index i, j;
  for (i=1; i <=n-1; i++){
  for (j = i+1; j <=n; j++ ){
  if( S[j] < S[i] ) { exchange S[i] and S[j] ; } } }
  단위연산 1) 조건문 S[j] < S[i] : j for루프 수행 때마다 1번씩 수행, T(n) = (n-1) + (n-2)+ .. + 1 = (n-1)n /2
  2) 교환하는 연산 exchange S[i] and S[j] : if 조건문이 참일 때 수행한다.
  최선의 경우 : 항상 거짓 (이미 비내림차순으로 정렬된 경우) -> T(n) =c
  최악의 경우 : 항상 참 (정렬 반대로 된 경우) -> T(n) = (n-1)n /2

• 예3) 순차검색, 문제: 비내림차 순으로 n개의 키를 정렬
  void seqsearch( int n, const keytype S[], keytype x, index&location ) {
  locatoin =1;
  while( location <= n && S[location] != x) { loaction++ ; } //배열안 위치하고 찾는게 x일때
  if (location >n ) { location =0; } //끝까지 찾았는데 없다.
  }
  단위연산 – 비교연산 S[location] != x

최악의 경우 x가 배열의 마지막이거나 없을 경우 W(n) = n , 순차검색의 경우 입력 배열의 값에 따라 검색하는 횟수 달라지므로 모든 경우 분석은 불가능하다.

평균의 경우, 배열의 아이템이 모두 다르다고 가정,
경우1) x가 배열 S안에 있는 경우만 고려 1≤k≤n 에 대해 x가 배열 k번째에 있을 확률 1/n
x가 배열 k번째에 있다면, k를 찾기 위해서 수행하는 단위연산의 횟수 k번 따라서 A(n) = 1/n n(n+1)/2
= (n+1)/2
경우 2) x가 배열 S안에 없는 경우도 고려, x가 배열S 안에 있을 확률 p 일 때 x가 배열 k번째에 있을 확률 p/n, x가 배열에 없을 확률은 1-p, 따라서 A(n) = p/n n(n+1)/2 + n(1-p) = n(1-p/2)+p/2
i) p=1일때 A(n) = (n+1)/2 (경우1과 동일) , ii) p=1/2, A(n) = (3n+1)/4

최선의 경우, 입력의 크기에 상관없이 단위연산이 1번만 수행된다. 따라서 B(n) = 1

• 알고리즘의 정확도 분석 : 의도한 대로 수행되는지 분석, 어떠한 입력에도 답을 출력하면서 멈춰야 정확함. 입력 데이터 크기가 작으면 알고리즘의 효율성이 중요하지 않아 비효율적인 알고리즘이어도 무방하나, 입력 데이터 크기가 충분히 크면 비효율적인 알고리즘은 치명적이다.

• 입력의 크기가 충분히 큰 경우에 대한 분석 ->점근적 분석(Asymptotic Analysis)

• 점근적 표기(Asymptotic Notation): 입력의 크기가 충분히 큰 경우에 대한 분석, 시간 (또는 공간)복잡도는 입력 크기에 대한 함수로 표기하는데, 주로 다항식이다. 이를 단순한 함수로 표현하기 위해 점근적 표기를 사용한다. 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다. Big-Oh Notaion

• Big-Oh Notaion : g(n) = O(f(n)) iff there exists two positive constants c>0 and n0 ≥1 ,
  s.t. |g(n)| ≤ c * |f(n)| for all n ≥n0

• Let A(n) = Then 상한선 이라고 생각

• O(1)< O(log n) < O(n) < O(nlog n) < O(n^2)O() < O(n^3) < O(2^n)

• 헷갈리는 예 ) n ⋲ O(n^2) 이고 3log n +8 ⋲ O(n^2) 이고 2nlog n⋲ O(n^2)이다.

• Big-Omega Notaion Ω Asymptotic Lower Bound 하한선
  g(n) = Ω(f(n)) iff there exists two positive constants c >0 and n0 ≥1
  s.t. |g(n) | ≥ c * |f(n)| for all n ≥n0
  어떤 함수 g(n)이 Ω(n^2) 에 속한다는 말은 그 함수는 궁극적으로 어떤 2차함수 cn^2의 값보다는 큰 값을 가지게 된다. 다시말해 그 함수 g(n)은 어떤 2차함수 보다는 궁극적으로 나쁘다 (기울기가 높다)고 할 수있다.
  어떤 알고리즘의 시간복잡도가 Ω(f(n))이라면, 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 f(n)밖에 되지 않는다. (하한) 다시말하면, 이 알고리즘의 수행시간은 f(n)보다 절대로 더 빠를 수 없다.

• 예) n^2+10n⋲Ω(n^2) , n^3⋲Ω(n^2) n^6⋲ Ω(n^2) 2^n+4n⋲ Ω(n^2)

• 증명 예) n⋲Ω(n^2) 가 아니다. n ≥c*n^2라고 가정, 그러면 n≥n0인 모든 정수 n에 대해 n⋲Ω(n^2)이 성립하는 양의 실수 c와 정수 n0가 존재한다. 위의 부등식 양변 cn으로 나누면 1/c ≥n 이다. 이 부등식은 성립할 수 없어서 가정의 모순이다.

• Big-Theta Notaion θ : Asymptotic tight Bound
  g(n) = θ(f(n)) iff there exists three positive constants c1,c2 and n0 ≥1
  s.t. c1 |f(n)|≤ g(n)| ≤ c2 |f(n)| for all n ≥n0
  즉, θ(f(n)) = O(f(n)) ∩ Ω(f(n))

• θ표기는 O표기와 Ω표기가 같은 경우에 사용한다.
  예) T(n) = n(n-1)/2은 O(n^2) 이면서 Ω(n^2)이다. 따라서 T(n) = θ(n^2)
  θ()

  3log n +8 ⋲ O(n^2)
  2nlog n⋲ O(n^2)
  n^3 ⋲ Ω(n^2)
  n^2+10n⋲ Ω(n^2) n^6⋲ Ω(n^2)

• 복잡도는 일반적으로 O-표기를 사용하여 표현하며 θ표기와 혼용하기도 한다.