자료구조2

🌝 자료구조와 알고리즘 성능

가상컴퓨터 + 가상언어 + 가상코드

• 가상컴퓨터(Virtual Machine) + 가상언어(Pseudo Language) + 가상코드(Pseudo Code)
• 가상 컴퓨터: Turing Machine (가장 처음 등장한 컴터)
• Von Neumann: RAM(Random Access Machine) 컴터 모델을 제시 (우리가 현재 쓰고있는 컴터 모델과 굉장히 비슷)
• RAM = CPU + Memory + 기본연산(단위시간(1시간)에 수행되는 연산)
• 기본연산 (1단위 시간 내 할 수 있는 연산)

• 배정연산, 대입연산
• 복사연산: A=B(B를 읽어 A를 쓰기)
• 산술연산: +, =, *, /(%, 반올림 연산 등 이런 연산은 RAM모델은 기본연산이라고 부르지 않음)
• 비교연산: >, >=, <=, ==, != (A<B <=> A-B < 0 비교를 한다는건 뺼셈을 한다는 것)
• 논리연산: And, Or, Not
• 비트연산: bit별로 And, Or, Not
  1단위 시간내 할 수 있는 기본연산으로 정의한 가상의 컴퓨터를 RAM모델이라고 부르며,
  RAM모델 위에서 알고리즘의 수행시간을 측정해서 그 측정된 시간을 비교할 것.

🌝 가상머신(가상컴터)위에 알고리즘을 동작시켜야하는데 그러면 가상컴터가 알아들을 수 있는 형태의 언어가 필요.
그 언어로 알고리즘을 기술해야함.
그 기술된 알고리즘이 가상머신위에서 돌아감.
RAM모델에서 제공하는 기본연산들을 표현할 수 있는 언어.
또한, 여러가지 제어할 수 있는 명령어들의 집합을 제공해주어야함.
그언어에 따라 코드를 작성하는 것 = 가상코드
그 가상코드가 가상머신위에서 돌아감. (시뮬레이션 됨)

🌝 가상언어(Pseudo/Virtual Languages).

• 배정연산, 산술연산, 비교연산, 논리연산, bit-논리연산 등 기본연산들을 표현하면 됨.
• 비교: if문, if-else문, if-elif...else구조.
• 반복: for, while
• 함수: 정의, 호출, return

🌝 가상코드(Pseudo Code)
algorithm ArrayMax(A,n):
input: n개의 정수를 저장한 배열A.
output: A의 수 중에서 최대값 찾아 리턴.

    A = [3,-1,9,2,12] n=5
    currentMax = A[0]
    for i in range(1,n):
    	if currentMax < A[i]
        	currentMax = A[i]
    return currentMax

A = [,,,,,,_] n:input size
1. 모든 입력에 대해서 기본연산 횟수를 더한 후 평균을 내는 것
-> 현실적으로 불가능해
2. 가장 안좋은 입력(알고리즘의 기본연산 횟수를 최대한 많이 필요로 하게 만드는 입력(Worstcase input)에 대한 기본 연산 횟수를 측정하기
-> Worstcase time complexity
-> 어떤 입력에 대해서도 Worstcase time complexity보다 수행시간이 크지않다.

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