📇 Table of Contents

---

1. 가상 컴퓨터, 가상 언어, 가상 코드, 기본 연산
2. 알고리즘의 시간 복잡도
3. Big-O 표기법 (업데이트 예정)
4. 참고 자료

1. 가상 컴퓨터, 가상 언어, 가상 코드, 기본 연산

---

객관적인 자료구조 및 알고리즘의 성능을 구하기 위해 추상화 된 개념이다.

가상 컴퓨터(Virtual Machine)

하드웨어나 소프트웨어의 성능에 상관없이
객관적으로 자료구조 및 알고리즘의 성능을 구하기 위해
추상화 된 가상의 컴퓨터.

해당 개념은 튜링의 Turing Machine에서 출발하여,
현대에 들어서는 폰 노이만의 Random Access Machine(이하 RAM)이라는 모델로 정착이 되었다.

가상 언어(Pseudo language)

가상 컴퓨터가 이해할 수 있는 가상 언어
즉, RAM에서 제공하는 기본 연산 및 명령어의 집합

1. 기본 연산 (아래 참고)
2. 비교 연산
   • if if else else if else
3. 반복문
   • for while
4. 함수
   • 정의 호출 return

가상 코드(Pseudo Code)

가상 언어로 작성되는 가상의 코드

예시)
input: n개의 정수를 갖는 배열 Arr
output: Arr의 요소 중 최댓값

algorithm MaxArray(Arr, n):
    Max = Arr{0]
    for i = 1 to n-1 do
    	if Max < Arr[i]:
        	Max = Arr[i]
	return Max

기본 연산

단위 시간에 수행 되는 연산의 집합

1. 배정, 대입, 복사 연산
   • =
     A = B와 같이 B을 '읽어'(메모리 접근) A에 '쓰는'(메모리 접근) 것을 다 합쳐서 하나의 단위 시간이라 가정한다.
2. 산술 연산
   • + - * /
   • 사칙연산이 이에 해당한다.
   • 나머지 연산, 반올림 연산, 올림/버림 연산은 여기에 해당하지 않는다.
3. 비교 연산
   • > >= < <= == !=
4. 논리 연산
   • AND OR NOT
5. bit-논리 연산
   • bit-AND bit-OR bit-NOT

위의 5가지의 연산을 각 1 단위 시간에 수행할 수 있는 컴퓨터를
가상의 컴퓨터를 RAM(Random Access Machine)이라 하자.

해당 RAM의 연산을 바탕으로 몇몇의 알고리즘을 수행하며,
알고리즘의 단위 시간을 측정하고 서로 비교할 것이다.

2. 알고리즘의 시간 복잡도

---

가정

'A'라는 알고리즘이 있다고 가정해 보자.
만약에 이 알고리즘에 대하여 시간 복잡도를 제대로 알고 싶다면,
가능한 모든 입력을 받아, 각 연산의 연산 횟수를 더한 이후,
이에 대한 평균을 내면 된다.

문제

BUT, 이는 현실적으로 불가능하다. 어떻게 모든 입력을 받을 수 있을까?
가능하다 할지라도 하나의 알고리즘에 대하여 하나의 시간 복잡도를 구하는데,
너무나도 많은 비용을 가져올 것이다.

해결

따라서 최악의 입력(worst-case input)에 대하여
기본 연산의 횟수를 측정하는 것이다.

이를 Worst-case time complexity라고 한다.

• 알고리즘의 수행시간 == 최악의 입력에 대한 기본 연산의 횟수

이것을 구하면, 이를 제외한 해당 알고리즘의 모든 연산 횟수는 worst-case time complexity보다 크지 않다.

3. Big-O 표기법 (업데이트 예정)

---

4. 참고 자료

---

(YouTube) Chan-Su Shin

• (자료구조 -Data Structures with Python) 알고리즘 시간복잡도1
• (자료구조 -Data Structures with Python) 알고리즘 시간복잡도2
• (자료구조 -Data Structures with Python) 알고리즘 시간복잡도 BigO

Wikipedia

• Worst-case complexity
• Big O notation

모두의 코드

• 모두의 알고리즘 - 1. 어떤 알고리즘이 효율적인가?