컴퓨터알고리즘#2

LeeMir, 03 March 2021

알고리즘 분석

알고리즘 분석
  • 알고리즘(Algorithm) : 주어진 문제를 유한한 시간내에 해결하는 단계적 절차
  • 데이터구조(Data Structure) : 데이터를 조직하고 접근하는 체계적 방식
  • 관심사 : “좋은” 알고리즘과 데이터구조를 설계하는 것
    • “좋은”의 척도
      • 알고리즘과 데이터구조 작업에 소요되는 실행시간(시간복잡도)
      • 기억장소 사용량(공간복잡도)
  • 어떤 알고리즘과 데이터구조를 “좋다”고 분류하기 위해서는, 이를 분석하기 위한 정밀한 수단을 필요로 한다.
실행시간
  • 대부분의 알고리즘은 입력을 출력으로 변환한다
  • 현재 시장에 점점 용량이 큰 메모리(저장 장치)들이 출시되고 있음에 따라, 알고리즘을 판단할 때 공간복잡도보다는 시간복잡도를 더 중요하게 여기게 되었음
  • 알고리즘의 실행시간은 입력의 크기(Input Size)에 비례
  • 실행시간에는 최적 실행시간, 평균 실행시간, 최악 실행시간이 있음
    • 최적 실행시간은 가장 운이 좋은 경우라고 할 수 있기 때문에 알고리즘의 실행시간을 대표한다고 볼 수 없다
    • 평균 실행시간은 “평균 입력”이라는 개념을 판단하기 어렵다
    • 최악 실행시간은 분석이 용이하고, 쓰임새가 다양해 알고리즘의 실행시간을 대표한다
  • 실행시간을 구하는 방법에는 실험적 방법과 이론적 방법이 존재
    • 실험적 방법
      • 알고리즘을 구현하는 프로그램을 작성
      • 프로그램을 다양한 크기와 요소로 구성된 입력을 사용하여 실행
      • 시스템콜(End time - Start time을 해주는 존재)을 사용하여 실제 실행시간을 정확히 측정
      • 결과를 도표로 작성
    • 실험적 방법의 한계
      • 실험 결과는 실험에 포함되지 않은 입력에 대한 실행시간을 제대로 반영하지 않을 수 있음
      • 두 개의 알고리즘을 비교하기 위해서는, 반드시 동일한 환경에서 사용되어야함
        • HW : processor, clock rate, memory, disk 등
        • SW : OS, prigramming language, compiler 등
      • 알고리즘을 완전한 프로그램으로 구현해야 하는데, 이것이 매우 어려울 수 있음
    • 이론적 방법
      • 모든 입력 가능성을 고려
      • 하드웨어나 소프트웨어와 무관하게 알고리즘의 속도 평가 가능
        • 실행시간을 입력 크기, n의 함수로 규정
      • 알고리즘을 구현한 프로그램 대신, 고급언어, 즉, 의사코드로 표현된 알고리즘을 사용
알고리즘의 정의와 조건
  • 입력(well defined input) : 모호하지 않고 잘 정의된 0개 이상의 입력
  • 출력(well defined output) : 명확하게 정의된 1개 이상의 출력
  • 명확성(clear and unambiguous) : 모호하지 않고 명확한 명령어
  • 유한성(finite) : 한정된 수의 단계 후 반드시 종료. 무한루프 X
  • 유효성(feasible) : 명령어들은 현재 실행 가능한 연산이어야 함
알고리즘 기술 방법
  • 자연어
  • 흐름도(Flowchart)
  • 의사코드(pseudo-code)
  • 프로그래밍 언어(C, Python…)
의사코드
  • 의사코드(pseudo-code) : 알고리즘을 설명하기 위한 고급언어
  • 자연어 문장보다 더 구조적이지만, 프로그래밍 언어보다는 덜 상세함
  • 알고리즘을 설명하는데 선호되는 표기법
  • 문법
    • var : 변수
    • arg : 인자
    • exp : 수식

    • [ x ] : x가 선택 사항

    • x y z : 택일
    • … : 임의의 명령문
    • x* : 0번 이상 반복 가능
    • 들여쓰기로 범위를 정의

    • 제어

      • if(exp) ...
[elseif(exp) ... ]*
[else ...]

      • for var <- exp1 to|downto exp2
	...

      • for each var ∈ exp
	...

      • while(exp)
	...

      • do
	...
while(exp)

    • 연산

      • <- : 치환

      • =, <, ≤, >, ≥ : 관계 연산자

      • &,   , ! : 논리 연산자
      • 첨자 등 수학적 표현 허용

    • 메쏘드(method) 정의, 반환, 호출

      • Alg method([arg [,arg]*])
	...

      • return [exp [,exp]*]

      • method([arg [,arg]*])
    • 주석 : { }로 표현
임의접근기계 모델
  • 임의접근기계(Random Access Machine. RAM) 모델
    • 이론적 방법으로 알고리즘의 실행시간을 측정하기 위한 가상의 모델
    • 하나의 중앙처리장치(CPU)
    • 무제한의 메모리셀(memory cell), 각각의 셀은 임의의 수나 문자 데이터를 저장함
  • 메모리셀은 순번으로 나열, 어떤 셀에 대한 접근이라도 동일한 시간단위가 소요됨
원시작업
  • 알고리즘에 의해 수행되는 기본적인 계산들
  • 의사코드로 표현 가능
  • 프로그래밍 언어와는 대체로 무관
  • 정밀한 정의는 중요하지 않음
  • 임의접근기계 모델에서 수행시 상수시간이 소요된다고 가정
  • 예시
    • 산술식/논리식의 평가 => EXP
    • 변수에 특정값을 치환 => ASS
    • 배열원소 접근 => IND
    • 메쏘드 호출 => CAL
    • 메쏘드로부터 반환 => RET