알고리즘 기초

지니·2022년 9월 26일
0

알고리즘

목록 보기
1/1

주요용어

  • 알고리즘 : 주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한유한개의 일련의 명령을 순서적으로 구성한 것
  • 시간 복잡도 : 알고리즘을 실행시켜 완료할 때까지 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 표현함
  • 접근성능 : 입력 크기의 n이 충분히 커질 때 결정되는 알고리즘의 성능으로, 점근적 상한 , 접근적 하한 등을 사용해서 표기함
  • 점화실 : 함수의 한 값이 자신을 포함한 수식으로 다시 표현된 식을 의미하며, 순환 형태의 알고리즘 수행 시간은 점화식으로 표현됨

알고리즘의 정의

▶ 주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것

▶ 조건(입출력, 명확성, 유한성, 유효성) + 실용적 관점에서의 추가 조건(효율성)

▶ 생성 과정 : 설계 → 표현(기술) → 정확성 분석 → 효율성 분석

  • 입출력 : 0개 이상의 외부 입력 → 1개 이상의 출력
  • 명확성 : 각 명령은 모호하지 않고 단순 명확해야 함
  • 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료
  • 유효성 : 모든 명령은 컴퓨터에서 수행 가능해야 함

알고리즘 표현/기술

최댓값 찾기 알고리즘

  • 일상언어
단계1. 첫 숫자를 최댓값으로 지정한다.
단계2. 다음 숫자를 읽고, 저장된 최댓값과 비교한다.
단계3. 비교 후 더 큰 숫자를최댓값으로 다시 저장한다.
단계4. 다음에 읽을 숫자가 남아 있으면 단계 2로 간다.
단계5. 저장된 숫자를 최댓값으로 출력한다.
  • 의사 코드 (pseudo code)
max = A[0];
for (i = 1 -> n)
	if (A[i] > max) max = A[i];
print(max)
  • flow chart

알고리즘 설계

▶ 주어진 문제와 조건 등이 매우 다양하므로 모든/대부분 문제에 적용할 수 있는 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법이 있음

  • 주어지는 문제, 속성, 조건 등이 매우 다양
    • 범용적인 설계 기법은 미존재
  • 대표적인 알고리즘 설계 기법
    • 분할정복 방법
    • 동적 프로그래밍
    • 욕싱쟁이 방법

알고리즘 분석

▶ 정확성 분석: 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지를 판단 → 수학적 기법을 사용해서 이론적으로 증명

▶ 효율성 분석: 공간 복잡도(알고리즘 수행에 필요한 메모리양), 시간 복잡도(알고리즘을 실행시켜 완료될 때까지 걸리는 시간)

▶ 시간 복잡도: 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 표현 → 최악의 수행 시간을 입력 크기의 함수로 표현

  • 정확성 분석
    • 유효한 입력, 유한 시간 ⇒ 정확한 결과 생성 여부 ?
      • 다양한 수학적 기법을 사용해서 이론적인 증명이 필요
  • 효율성 분석
    • 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
    • 메모리 양 → 공간 복잡도
      • 정적 공간 + 동적 공간
    • 수행 시간 → 시간 복잡도

시간 복잡도

  • 구현한 알고리즘을 컴퓨터에서 실행시켜 실제 수행 시간 측정
    • 일반성 결여
      • 컴퓨터의 속도, 프로그래밍 언어, 프로그래밍 작성 방법, 컴파일러의효율성등에 종속성
    • 시간 복잡도 ⇒ “알고리즘의 단위 연산의 수행 횟수의 합”
      • 시간 복잡도에 영향을 미치는 요인
        • 입력 크기
          • 입력으로 제공되는 데이터의 크기, 문제가 해결하려는 대상이 되는 개체의 개수
          • 예: 행렬의 크기, 리스트 원수의 수, 그래피의 정점의 수
        • 입력 데이터의 상태
  • 입력 크기 n이 증가하면 수행 시간도 증가
    • 단순히 수행되는 단위 연산의 개수의 합으로 표현하는 것은 부적절
      • 입력 크기 n에 대한 함수 f(n)으로 표현
  • 입력 데이터의 상태에 종속적
    • 평균 수행 시간
    • 최선 수행 시간
    • 최악 수행 시간
  • 요약 : 시간 복잡도는 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 표현하는데, 입력 크기 n에 대한 함수 f(n)으로 표현하고 최악의 수행 시간을 가지고 표현한다.

Big-oh 표기

f(n) = 3n + 5 ⇒ O(n)

점근성능

▶ 입력 크기 n이 무한히 커짐에 따라 결정되는 성능 → 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현 → 알고리즘의 수행 시간의 증가 추이를 나타내는 것으로 알고리즘의 우열 관계를 따질 때 용이

▶ 표기법 : ① “Big-oh” 점근적 상한 f(n) = O(g(n)), ② “Big-omega” 점근적 하한 f(n)=Ω(g(n)), ③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))

▶ O-표기 간의 연산 시간의 크기 관계 : O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)

  • 입력 크기 n이 무한대로 커짐에 따라 결정되는 성능
    • f(n) = 10n + 9
    • f(n) = n/2+3n
    • f(n) = 2n^2 + 5n + 200
  • 점근성능의 결정 방법
    • 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
      • 수행 시간의 정확한 값이 아닌 어림값
        • 수행 시간의 증가 추세를 파악하는데 용이
        • 알고리즘의 우열 표현이 용이

점근성능의 표기법

‘Big-oh’ 점근적 상한

  • 함수 f와 g를 각각 양의 정수를 갖는 함수라 하자.
  • 어떤 양의 상수 c와 n₀이 존재하여, 모든 n≥n₀에 대하여 f(n)≤c*g(n)이면 f(n)=O(g(n))이다.
  • 최악의 수행 시간

‘Big-omega’ 점근적 하한

  • 함수 f와 g를 각각 양의 정수를 갖는 함수라 하자.
  • 어떤 양의 상수 c와 n₀이 존재하여, 모든 n≥n₀에 대하여 f(n)≥c*g(n)이면 f(n)=Ω(g(n))이다.
  • 최선의 수행 시간

‘Big-theta’ 점근적 하한

  • 함수 f와 g를 각각 양의 정수를 갖는 함수라 하자.
  • 어떤 양의 상수 c₁, c₂와 n₀이 존재하여, 모든 n≥n₀에 대하여 c₁*g(n)≤f(n)≤c*g(n)이면 f(n)=Θ(g(n))이다.

예) f(n) = 3n + 5, g(n) = n

  • n₀=2, c=11이면 n≥2에 대해서 3n+5 ≤ 11*n → f(n) = O(g(n)) = O(n)
  • n₀=1, c=3이면 n≥1에 대해서 3n+5 ≥ 3*n → f(n) = O(g(n)) = Ω(n)
  • f(n) = O(n) 그리고 f(n) = Ω(n) → f(n) = Θ(n)

주요 0-표기 간의 연산 시간의 크기 관계

  • 상수 시간 < 로그 시간 < 성현 시간 < 로그 성형 시간 < 제곱 시간 < 세제곱 시간 < 지수 시간
  • O(1) < 0(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

알고리즘의 시간 복잡도 구하기

  • 알고리즘의 시간 복잡도를 구하려면
    • 알고리즘의 수행 시간 f(n)을 구한 후,
    • f(n)=O(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾음
  • 실용적인 접근 방법
    • 알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도를 취함

순환 알고리즘의 성능

순환

  • 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태
  • T(n) = T(n/2) + O(1), T(1) = c₁

기본 점화식과 폐쇄형

▶ 분할정복 방법을 적용한 알고리즘은 기본적으로 순환 알고리즘의 형태로 표현되고, 순환 알고리즘의 성능은 점화식으로 표현됨

▶ 기본 점화식과 폐쇄형

① T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)

② T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n2) → 퀵 정렬의 최악 수행 시간

③ T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn) → 이진 탐색의 수행 시간

④ T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)

⑤ T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)

⑥ T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn) → 퀵 정렬의 최선 수행 시간, 합병 정렬의 수행 시간

Reference

한국방송통신대학교 컴퓨터과학과 알고리즘 강의(이관용)

profile
오늘도 호기심을 발휘한다!

0개의 댓글