알고리즘 시간복잡도 1

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

 

 

자료구조 + 알고리즘 --> [[[코드(C, java, Python)]  컴퓨터]  HW/SW 환경 상이] 

또한, 다양한 크기의 입력이 존재함. 

알고리즘별로 빠르고 느린 입력이 다르다.

 

Q. 내가 작성한 코드가 얼마나 빨리 동작하는가를 객관적으로 어떻게 측정하는가?

- 가상컴퓨터 (Virtual Machine) + 가상언어 (Pseudo language) + 가상코드 (Pseudo Code)

--> 누구나 같은 환경에서 여러 알고리즘을 객관적으로 비교할 수 있게 됨.

 

1. 가상컴퓨터

Turing Machine -> von Neumann: RAM(Random Access Machine)

RAM = CPU + Memory (CPU의 계산 수행, 메모리에는 프로그램과 데이터가 저장됨)

어떤 식으로 메모리에 있는 데이터를 가공할 것인가? 이것이 코드

RAM = CPU + Memory + 기본연산

RAM Model

 

기본연산의 종류 (모두 1시간(단위시간) 내에 이루어짐) 

• 배정, 대입, 복사연산: A = B 
• 산술연산: +,-,*,/ 
• 비교연산: >, >=, <, <=, ==, !=
• 논리연산: AND, OR, NOT
• 비트연산: bit-AND, OR, NOT 

 

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

가상컴퓨터가 알아들을 수 있는 형태의 언어

RAM model에서 제공하는 기본연산을 수행할 수 있어야 함.

• 배정, 산술, 비교, 논리, bit-논리 연산을 표현할 수 있으면 됨. 
• if, if else, if elseif(elif)....else (제어할 수 있는 명령어 필요)
• 반복문 for, while
• 함수 정의 및 호출, return

 

3. 가상코드 (Pseudo Code)

ex)

algorithm ArrayMax(A,n):     # 지금부터 ArrayMax라는 가상의 코드를 기술하겠다
	input: n개의 정수를 받는 배열 A 
    output: A의 수 중에서 최대값 리턴
	currentMax = A[0]
    for i=1 to n-1 do
    	if currentMax < A[i]:
        currentMax = A[i]
	return currentMax

Q. 만약 위 가상함수에 array A = [3, -1, 9, 2, 12] (n=5)가 주어진다면, 기본연산을 몇 번 수행할까?

*for문 내부적으로 하는 기본연산은 세지 않음. 

기본연산은 7회 이루어짐. 즉 7만큼의 단위시간이 필요하다. 

 

무한히 많은 입력과 무한히 많은 n (n도 무한히 많음)

그 때마다 기본연산의 수행 횟수를 세는 것은 사실상 불가능.

 

그럼 이 때에는 어떻게 내 알고리즘을 판단해야 하나?

--> 다음 파트에서 이어짐.