알고리즘1-1. 알고리즘이란?

알고리즘이란?

- ‘문제나 과제를 해결하기 위한 처리 절차를 하나하나 구체적인 순서에 따라 표현한 아이디어나 생각’

 

알고리즘의 조건

입력	외부에서 제공되는 자료가 0개 이상 존재한다.
출력	적어도 2개 이상의 서로 다른 결과가 나와야 한다. (즉 모든 입력에 하나의 출력이 나오면 안된다.)
명확성	수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성(종결성)	유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
효율성	모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

 

프로그램 작성의 흐름(프로그램 알고리즘)

- 기획 → 설계 → 프로그래밍(코딩) → 디버깅 → 문서 작성

---

1. 알고리즘 성능

- 좋은 알고리즘의 분석 기능

 

정확성	얼마나 정확하게 동작하는가?
작업량	얼마나 적은 연산으로 원하는 결과를 얻어내는가?
메모리 사용량	얼마나 적은 메모리를 사용하는가?
단순성	얼마나 단순한가?
최적성	더 이상 개선할 여지없이 최적화되었는가? (가장 좋은)

 

2. 복잡도(접근 표기법: Big-O Notation)

- 프로그램의 실행속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity) 라고 한다.

 

시간 복잡도(time complexity)	실행에 필요한 시간을 평가한 것
공간 복잡도(space complexity)	기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

복잡도	설명
O(1)	입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
O(log N)	입력 자료의 크기가 N일 경우 log2N 번만큼의 수행시간을 가진다.
O(N)	입력 자료의 크기가 N일 경우 N번 만큼의 수행시간을 가진다.
O(N log N)	입력 자료의 크기가 N일 경우 N*(1og2N)번만큼의 수행시간을 가진다.
O(N2)	입력 자료의 크기가 N일 경우 N2번만큼의 수행시간을 가진다.
O(N3)	입력 자료의 크기가 N일 경우 N3번만큼의 수행시간을 가진다.
O(2n)	입력 자료의 크기가 N일 경우 2N번만큼의 수행시간을 가진다.
O(n!)	입력 자료의 크기가 N일 경우 n*(n-1)*(n-2)…*1(n!)번만큼의 수행시간을 가진다.

 

 

<각기 다른 시간 복잡도의 알고리즘을 나타낸 그래프>

 

 

빅-오(O) 표기법

- 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만 표시한다.

- 계수는 생략하고 표시한다.

 

O(3n+2) = O(3n) = O(n)

O+10n+100) = O(O+10n+100) = O(

O(4) = O(1)