자료구조와 알고리즘

똑같은 알고리즘이라도 HW/SW 환경이 상이하여 속도가 다르다. 또한 다양한 크기를 입력하기에 내가 만든 알고리즘이 얼마나 빠르게 작동하는지 알 필요가 있다.

우선 독립적인 가상 컴퓨터를 설정 : virtual machine
이 가상의 컴퓨터에서 가상언어(Pseudo language)로 알고리즘을 기술
이 가상언어로 기술한 것을 가상코드(Pseudo Code)
라고 한다.

이를 통해 객관적으로 비교한다.

가상 컴퓨터 : 폰 노이만의 Turing Machine : RAM(Random Access Machine)
RAM이라는 컴퓨터 모델 = CPU(계산을 실행하는 유닛) + Memory(CPU가 메모리에 접근해서 기본연산으로 읽고 쓰고 한다.) + 기본연산(단위시간에 수행되는 연산들의 모음)

Q. 기본연산? 1단위 시간 내에 할 수 있는 연산
배정, 대입, 복사 연산 등
산술 연산(+,-, * , / )
비교 연산(>, <, =, <=)
논리 연산(AND, OR, NOT)
비트 연산(bit-AND, OR, NOT)

가상 언어(Pseudo/Virtual Languages)
실제로 사용되는 프로그래밍 언어일 필요는 없고, 문법적으로 조금 느슨한 아무 언어.
1)배정, 산술, 비교, 논리, bit논리 연산 등을 표현할 수 있으면 된다.
2)비교(if, else, elif, 등)
3)반복문(for, while)
4)함수를 정의, 호출, return 가능

이 가상 언어로 코드를 작성하면 그것이 가상 코드 Pseudo Code

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

https://www.youtube.com/watch?v=ysn9dLDNLEU&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=4