자료구조와 알고리즘 with 파이썬 chapter5. 알고리즘 개요

5-1 알고리즘이란?

알고리즘의 정의와 조건

- 알고리즘은 주어진 문제를 해결하기 위한 단계적인 절차, 일을 수행하는 명령어들의 집합. 

조건

1. 입력: 모호하지 않고 잘 정의된 입력.
2. 명확성 : 각 명령어의 의미가 모호하지 않고 명확해야함.
3. 언어 독립성 : 프로그래밍 언어와 상관없음.
4. 출력 : 명확히 정의된 1개 이상의 출력
5. 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야함.
6. 유효성 : 명령어들은 현재 실행 가능한 연산이어야 함. 

알고리즘의 기술 방법

• 영어나 한국어와 같은 자연어를 사용하는 방법: 표현이 자유롭고 편리하다는 장점이 있지만, 자칫 문장의 의미가 애매해질 수 있다. 
• 흐름도로 표시하는 방법 : 알고리즘의 절차들을 가장 정확하게 표현가능. 하지만 알고리즘이 조금만 길어도 그림이 너무 복잡해져 혼란스로워진다. 
• 특정한 프로그래밍 언어의 코드로 나타내는 방법 : 알고리즘을 실행해 볼 수 있어 편리. 언어의 특징에 따른 많은 불필요한 표현들이 알고리즘에 포함된다. 
• 유사 코드로 기술하는 방법 : 자연어보다는 체계적이지만 프로그래밍 언어보다는 덜 엄격하다. 프로그래밍 언어에서 발생하는 많은 불필요한 표현을 생략가능. 

5-2. 알고리즘의 성능분석

• 연산량 : 알고리즘이 얼마나 적은 연산을 수행하는가? -> 알고리즘의 시간효율성
• 메모리 사용량 : 얼마나 적은 메모리 공간을 사용하는가? -> 공간효율성

실행시간 측정 방법

import time
start = time.time()
testAlgorithm(input)
end = time.time()
print("실행시간 = ", end-start)

약점

• 알고리즘은 반드시 '구현'해아 한다. 알고리즘이 비교적 단순하다면 어렵지 않겠지만, 복잡한 경우에는 구현이 큰 부담이 될 수 있다.
• 여러 알고리즘의 측정 결과를 비교하기 위해서는 반드시 같은 조건의 하드웨어를 사용.
• 프로그래밍 언어나 운영체제와 같은 소프트웨어 환경도 같아야 한다.
• 성능 비교에 사용했던 데이터가 아닌 다른 데이터에 대해서는 전혀 다른 결과가 나올 수 있어 실험되지 않은 입력에 대해서는 실행 시간을 주장할 수 없다. 

복잡도 분석 방법

- 연산의 실행 횟수는 입력 크기 n에 대한 함수 형태, 즉 T(n)으로 나타낸다.-> 복잡도 함수

- 1부터 n까지 합을 구하는 알고리즘 1

clac_sum1(n)
	sum ← 0
    for i ← 1 to n then
    	sum ← sum + i
    return sum

- 1부터 n까지 합을 구하는 알고리즘 2

calc_sum2(n)
	sum ← n * (n+1) / 2
    return sum

• 알고리즘 1 : 2행에서 대입연산이 한 번 수행. 반복문 내부인 4행은 n번 수행 되는데, 대입과 덧셈 연산을 한 번씩 수행. 2행과 4행의 연산 실행 횟수를 보두 합하면 2n+1이 되고, 복잡도 함수는 T1(n) = 2n + 1로 나타낼 수 있다.
• 알고리즘 2 : 모든 행이 한 번만 수행. 4번의 연산이 필요하고,(대입, 곱셈, 덧셈, 나눗셈) 복잡도 함수는 T2(n) = 4이다. 

- n이 커질수록 알고리즘 2가 알고리즘 1보다 훨씬 효율적이다. 

점근적 표기

• 빅오(big - O) 표기법
  • O(g(n))은 증가속도가 g(n)과 같거나 낮은 모든 복잡도 함수를 포함하는 집합. 알고리즘의 복잡도가 O(n^2)라면 이 알고리즘은 어떤 경우에도 n^2에 비례하는 시간 안에는 반드시 완료된다.
• 빅오메가(big-omega)표기법
  •  

은 증가 속도가 g(n)과 같거나 높은 모든 복잡도 함수를 포함. 

• 빅세타(big-theta)표기법

O(1) < O(logn) < O(n) < O(nlogn) < O(n^) < O(n^3) < O(2^n) < O(3^n) < O(n!)

최선, 최악, 평균적인 효율성

• 최선의 경우 : 실행 시간이 가정 적은 경우
• 평균적인 경우 : 알고리즘의 모든 입력을 고려하고 각 입력이 발생할 확률을 고려한 평균적인 실행시간.
• 최악의 경우 : 입력의 구성이 알고리즘의 실행 시간을 가장 많이 요구하는 경우.