알고리즘 성능

컴퓨터 알고리즘 성능 

 

알고리즘의 일반적인 정의 

문제를 해결하기 위한 절차를 공식화한 형태로 표현한 것.

 

컴퓨터 알고리즘의 요건

입출력

0개 이상의 외부 입력과 1개 이상의 출력이 필요하다.

a =3 					a = int(input())
b = 4					b = int(input())

c = a+b					c = a+b
print(c)				print(c)

  프로그램의 결과가 출력문이 프린트 문을 수행한 것은 아니다. 더하기 문제에 대한 결과를 출력한 것은 c변수에 더하기 연산을 한 결과를 저장하는 것이다. 이때 프린트 명령문은 컴퓨터가 제대로 수행하였는지의 결과를 직접 확인하고자 하는 명령문이지 프로그램에 전혀 영향을 미치는 것은 아니다.

=> 컴퓨터 알고리즘에서 입력과 출력은 외부 입출력이 아닌 겨로가를 얻기 위한 데이터 저장과 결과 데이터 저장임을 이해해야 한다. 두 번쨰 더하기 문제 파이썬 코드는 입력을 사용자가 키보드로 직접 입력할 수 있도록 프로그램의 '형식'을 바꾸었을 뿐 더하기 문제를 해결한 알고리즘 형식에는 변화가 없음을 알 수 있다.

 

 

 

정확성 / 유한성 / 수행성

"컴퓨터 알고리즘은 모든 입력값 n에 대해 유한 시간 내에 정확한 결과를 내야 한다."

   만들어진 알고리즘이 문제에 대한 모든 입력값에 대해서 유한 시간 내에 정확한 결과를 내는지 확인 하는 방법이 알고리즘의 효율성을 알아보는 것이다. 이때 비용 단위는 시간과 메모리 공간으로 정의한다. 시간은 프로그램 수행 시간, 연산을 수행하는데 드는 시간 비용을 말하며, 메모리 공간은 프로그램을 수행하는 동안 사용하는 주기억장치의 데이터 저장 공간을 말한다. 이를 알고리즘의 복잡도라 하고, 수행 시간 알고리즘 성능은 입력 크기에 대한 수행 시간 함수로 표현하며, 메모리 공간 알고리즘 성능은 입력 크기에 대한 메모리 사용공간 함수로 표현한다.

  시간 복잡도는 알고리즘을 수행할 떄 수행되는 연산의 횟수이다. 수행 시간에 대한 컴퓨터 알고리즘 성능을 계산 할 때 수행 시간은 연산의 횟수로 계산하며, 이떄 연산은 프로그래밍에서 사용되는 기본 연산을 말한다. 비교 연산, 읽기 연산, 데이터 갱신 연산, 산술 연산 등을 포함한다. 연산한다는 것은 알고리즘이 수행된다는 것이고, 수행되는 시간은 연산의 횟수에 직접적인 영향을 받는다. 

  공간 복잡도는 알고리즘을 수행할 때 필요한 메모리의 양이다. 메모리의 양은 알고리즘이 수행되는 동안 저장될 데이터의 양과 형을 의미하며, 연산 중에 임시로 저장되는 모든 데이터의 저장 공간도 포함된다. 컴퓨터로 문제를 해결하기 위해서는 반드시 데이터가 주기억장치에 저장되어야 하는데 저장한다는 것은 메모리 영역을 사용한다는 의미이므로, 알고리즘이 수행될 때 사용하는 메모리기 공간의 양으로 알고리즘의 성능을 확인할 수 있다.  

 

 

1~n까지의 정수의 합 구하는 문제

 수를 하나 가져온다 

  : 수를 저장한다. 새로운 수를 저장한다.

 수를 더한다

  : 이전에 더한 결과에 저장된 수를 더한다.

 

저장 = 주기억장치 공간 마련

 

 

같은 점

마지막 정수값을 입력받는 방법은 모두 input() 표준 입력

결과 저장 공간을 hap이라는 변수로 초기화 함 // 더해질 수를 저장할 변수로 저의한 것이 차이는 있으나 .

num = int(input())

a = 0
hap1 = 0

while a <=num :
	hap1 = hap1+a
    a+=1
    
print(hap1)

A : 더해질 수 저장 공간

while 반복문.

 

num = int(input())
hap2 = 0
for i in range(1, num) :
	hap2 = hap2+1
    
print(hap2)

i 이터널 변수 : 더해질 수 저장 공간

for문 문법 특징 : 저장 변수 변화 가능

 

num = int(input())
num_list=[]

b = 1
hap3 = 0

while b<=num :
	num_list.append(b)
    b+=1
    
for i in num_list :
	hap3 = hap3+i
    
print(hap3)

b : 리스트 생성 / 실제 정수 모두 저장

i : 더해질 수 인용 공간 

 

 

 

----

공간 복잡도

1,2 : a(=i), hap1, num 3개이며 각각 정수형 데이터를 1개씩 저장

 

3 : num, b, hap3 은 각각 정수형 데이터 1개씩 저장

num_list 는 계산 대상 모든 정수가 저장된다.

 

시간 복잡도

'' 횟수 기준 : 정수 데이터 1개마다 수행되는 연산자의 수행 횟수 ''

 

1 : 비교 연산 1회, 더하기 연산 2회 

2 : i값 갱신 1회, 더하기 연산 1회 

(range()와 같은 함수 연산도 포함되어야 하지만 지금은 기본연산 기준으로 시간 복잡도를 설명하고자 하기에 생략하였다.

일반 컴퓨터 과학에서 다루는 알고리즘은 함수를 사용하지 않고 갱신 연산을 직접구현)

3 : 비교 연산 1회, 데이터 추가 연산 1회, 더하기 연산 2회

 

  첫번째 반복문) 데이터의 수만큼 비교 1, 갱신 1, 더하기 1

  두번쨰 반복문) 데이터의 수만큼 갱신 1, 더하기 1

=> 각 반복문의 하위 연산은 제시된 횟수만큼 반복 : N

 

1 : 3n // 2 : 2n // 3 : 5n

1,2,3 시간 복잡도 함수는 다르지만 세 알고리즘 코드의 성능은 같다.

=> 알고리즘 성능은 빅 오 표기범을 이용하여 O(n) 로 똑같이 정의된다.

 

빅 오 표기법

왜 코드의 성능의 같은가?

 

시간 복잡도 표현 방법 

최선의 경우(Best) : 가장 빠른 시간

최악의 경우(Worst) : 가장 느린 시간

평균의 경우(Average) : '총 실행 시간/시행 횟수'

 

Big O = 최악의 경우 성능 표현

 = 함수의 상한만 표현 

 = 전체 성능에 큰 영향을 미치지 않는 수식은 제외하고 영향을 미치는 수식만 표현하기에 대충 표기법이라고도 함

  일반적으로 사용할 수 있는, 응용하여 문제 해결에 도움받을 수 있는 알고리즘들은 k차 시간 성능의 알고리즘까지이며, 다항시간 알고리즘이라고 한다. 이와달리 알고리즘이지수 시간 성능을 보인다면 그 알고리즘은 사용할 수 없는 알고리즘이며, 그러한 알고리즘으로 해결된 문제는 '해결되지 않은 문제'이다.

  위의 기준의 근거로는 첫째, 지금까지컴퓨터에서 처리할 데이터의양이 한번에 10억개가 되지 않기 때문이며, 현재 소프트웨어에서 처리해야 할 데이터의 양이 그정도로 많지 않기 때문이다. 많다 하더라도 데이터를 작게 분해하거나, 데이터 편집을 통해 충분히 알고리즘 자체 성능을 최고치로 올릴 수 있기 때문이다. 두번째는 하드웨어 성능을 높혀 충분히 실행 가능한 수행 시간으로 낮출 수 있기 때문이다.

  

  다음은 그 예시이다