Data Structure and Algorithm: Algorithm, Data Structure, Time Complexity

문제를 해결하는 과정은 ‘입력-문제해결(알고리즘)-출력’으로 이루어진다. 입력을 받은 ‘자료구조’를 통해 내가 찾고자하는 자료를 ‘알고리즘’을 통해 찾는 과정이다. 자료구조와 알고리즘은 서로 필수불가결 관계이다.

Algorithms

알고리즘은 문제의 입력(input)을 수학적이고 논리적으로 정의된 연산과정을 거쳐 원하는 출력(output)을 계산하는 절차이고, 이 절차를 프로그래밍 언어로 표현한 것이 프로그램(program) 또는 코드(code)가 된다.

Virtual Machine, Pseudo Language, Pseudo Code

자료구조와 알고리즘의 성능(performance)은 대부분 수행시간(시간복잡도: time complexity)으로 정의되는 것이 일반적이다. 이를 위해, 실제 프로그래밍 언어의 문법으로 구현하여 실제 컴퓨터에서 실행한 후 수행시간을 측정할 수도 있지만, HW/SW을 하나로 통일해야 하는 어려움이 있다. 따라서, 가상언어로 작성된 가상코드가상컴퓨터에서 시뮬레이션하여 HW/SW에 독립적인 계산 환경(Computational Model)에서 측정해야 한다.

Virtual Machine (가상 컴퓨터)

현대 컴퓨터 구조는 Turing machine에 기초한 폰 노이만 구조를 따른다. 요즘 가장 많이 사용하는 가상컴퓨터 모델은 (real) RAM(Random Access Machine)모델이다. 이는 Random Access Memory와 개념적으로 별 차이가 없다.

(real) RAM모델은 CPU+memory+primitive operation으로 정의된다.

  • CPU: 연산(operation, command)을 수행
  • memory: 임의의 크기의 실수도 저장할 수 있는 무한한 개수의 레지스터(register 또는 word)로 구성
  • primitive operation: 단위 시간에 수행할 수 있는 기본 연산의 집합. 기본연산 1번은 1 단위시간이 걸린다.
    • 배정/복사 연산 (A=B; B의 값을 A 레지스터에 복사)
    • 산술연산 (+,-,*,/)
    • 비교연산 (>, >=, <, <=, ==, !=)
    • 논리연산 (AND, OR, NOT)
    • 비트연산 (bit-AND, bit-OR, bit-NOT, bit-XOR, «, »)

Pseudo Language (가상 언어)

가상언어는 영어와 한국어와 같은 실제 언어보다는 간단 명료하지만 C나 JAVA 같은 프로그래밍 언어보다는 융통성있는 언어로 Python과 유사하게 정의한다.

  • 기본 명령어
    • 배정/복사 연산 (A=B; B의 값을 A 레지스터에 복사)
    • 산술연산 (+,-,*,/)
    • 비교연산 (>, >=, <, <=, ==, !=)
    • 논리연산 (AND, OR, NOT)
    • 비트연산 (bit-AND, bit-OR, bit-NOT, bit-XOR, «, »)
    • 비교문 (if, if else, if elseif … else 문)
    • 반복문 (for문, while 문)
    • 함수정의, 함수호출
    • return 문

Pseudo Code (가상 코드)

가상코드는 한마디로 가상언어로 작성된 코드이다. 컴퓨터 프로그램의 작동 원리 또는 알고리즘을 형식이 정해져 있지 않은 고차원(high-level) 언어로 기술한 코드를 일컫는다. 대개는 일정한 규칙을 준수하지만 기계가 판독하려는 용도가 아닌, 사람이 쉽게 알아볼 수 있는 형태로 기술한다.

알고리즘의 시간 복잡도

가상 컴퓨터에서 가상언어로 작성된 가상코드를 실행(시뮬레이션)한다고 가정한다. 수행시간은 특정 입력에 대해 수행되는 알고리즘의 기본연산(primitive operation)의 횟수로 정의한다. 문제는 입력의 종류가 무한하므로 모든 입력에 대해 수행시간을 측정하여 평균을 구하는 것은 현실적으로 가능하지 않는다는 점이다. 따라서, 최악의 경우의 입력(worst-case input)을 가정하여, 최악의 경우의 입력에 대한 알고리즘의 수행시간을 측정한다.

알고리즘의 수행시간 = 최악의 경우의 입력에 대한 기본연산의 수행 횟수 (at 가상컴퓨터 모델)

최악의 경우의 수행시간은 입력의 크기 $n$에 대한 함수 $T(n)$으로 표기한다. $T(n)$의 수행시간을 갖는 알고리즘은 어떠한 입력에 대해서도 $T(n)$ 시간 이내에 종료됨을 보장한다. 최악의 경우에서 입력에 대해 알고리즘의 기본연산(복사, 산술, 비교, 논리, 비트논리)의 횟수를 센다.

Big-O 표기법

최악의 입력에 대한 기본연산의 횟수를 정확히 세는 건 일반적으로 귀찮고 까다롭다. 정확한 횟수보다는 입력의 크기 n이 커질 때, 수행시간의 증가 정도(rate of the growth of $T(n)$ as $n$ goes big)가 훨씬 중요하다. 최고차 항만 남기고 나머지는 생략하는 식으로 수행시간을 간략히 표기하는 방법을 근사적 표기법(Asymptotic Notation)이라 하고 Big-O(대문자 O)를 이용하여 표기한다. ex) $T(n) = 2n + 5 $ :arrow_forward: $T(n)=O(n)$

  • Big-O Notation
    • $n$이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략한다.
    • 가장 빨리 증가하는 항에 곱해진 상수 역시 생략한다.
    • 남은 항을 $O()$ 안에 넣어 표기한다.

image

업데이트:

댓글남기기