알고리즘 시간복잡도1

해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하며 작성되어 있습니다. 🙏🏻

자료구조와 알고리즘 성능1: 가상컴퓨터 + 가상언어 + 가상코드

자료구조와 이를 해결하기 위한 알고리즘이 어느 정도의 성능을 보이는지 측정하고 비교해보자.

현실의 문제점

문제 1

• "자료구조"와 "알고리즘"을 생각하여 코드(C, Javascript, Python 등)로 구현하면 컴퓨터에서 동작하게 되지만,
• 각 컴퓨터마다 HW/SW 환경이 다를 수 있으므로 다른 성능을 낼 수 있다

-> 즉 이는 큰 문제가 될 수 있다.

문제 2

• 입력의 크기가 다양할 수 있다.
• 입력이 커질 수록 실행 시간도 많아지는데, 이 입력에 대해 코드 실행속도를 어떻게 정의하고 비교할 수 있을까?

해결책

가상의 컴퓨터(Virtual Machine) + 가상언어(Pseudo language) + 가상코드(Pseudo Code) 를 사용하자.

이렇게 하면 HW/SW 환경에 독립적이기 때문에 누구나 같은 환경에서 알고리즘을 객관적으로 비교할 수 있게 된다.

가상컴퓨터

가상 컴퓨터(Virtual Machine/Random Access Machine)
Turing Machine -> von Neumann: RAM(Random Access Machine)

RAM = CPU + Memory + 기본연산(단위시간에 수행되는 연산들의 모음)

즉, CPU와 Memory와 함께 계산을 하는 것이 알고리즘이고,
알고리즘이 RAM이라는 가상컴퓨터 위에서 돌아가는 것!

RAM은 가상의 컴퓨터 환경으로써 알고리즘 성능을 측정하는 기준 플랫폼이다.

기본연산

배정, 대입, 복사 연산 등과 같이 일반적으로 한 단위 시간 안에 수행되는 연산

1. A = B (Read and Write)
2. 산술연산: +, -, *, / (%, 내림, 올림, 반올림 등은 기본 연산으로 보지 않으나, 수업에서는 이들도 단위시간에 들어가는 것으로 간주)
3. 비교연산: >, >=, <, <=, ==, !=
4. 논리연산: AND, OR, NOT
5. 비트연산: bit-AND, OR, NOT

즉, 우리는 기본연산으로 정의한 가상의 컴퓨터를 RAM이라고 칭하고,
이 RAM 모델 위에서 알고리즘이 실행되고 측정되는 시간을 비교하는
알고리즘 복잡도를 계산하고 비교할 것이다.

가상 언어 (Pseudo/Virtual Languages)

1. 배정, 산술, 비교, 논리, bit-논리 연산 등 기본연산을 표현할 수 있으면 됨
2. 비교: if, if else, if elseif... else 등
3. 반복: for, while 등
4. 함수: 정의, 호출, 반환 문법

가상코드 (Pseudo/Virtual Code)

1. 실제 돌아가는 코드가 아닌 가상머신(RAM)에서 돌아가는 코드이므로 자유롭게 기술할 수 있다.