제 방식대로, 책 또는 위키 등의 교육자료 토대로 C 게시판을 써 나가보겠습니다.
알고리즘 : 문제를 해결하기위한 여러 동작의 모임. 유한성을 가지며, 언젠가는 끝나야 한다. 그리고 아래 조건을 만족해야만 한다.
입력 : 외부에서 제공되는 자료가 0개 이상 존재.
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성 : 유한 번의 명령어를 수행 후 시간 내 종료한다.
효율성 : 모든 과정은 명백하게 실행 가능한 것이어야 한다.
이는 오토마타와 관련이 있다.
뭐 정의는 이러 합니다. 너무 어렵다 생각되시는 분들은, 코드를 얼마나 더 효율적으로 짜느냐에 대하여 촛점을 맞추고 다시 읽어보시면 편합니다.
그러나, 알고리즘의 분석기준은 생각보다 복잡한데요,
입력이 적당한가, 올바른 답을 찾는가, 작업량이 얼마인가, 연산이 얼마나 있는가, 기억 장소 사용량은 어떠한가 등이 되겠습니다. 단어로 나열하자면
정확성, 작업량, 최적성(not well-known, mean best) 가 되겠네요.
저 알고리즘의 효율이 얼마나지? 라고 묻는걸 수치적으로 물을수도 있습니다.
저 알고리즘의 빅오(Big O)가 어떻게 되? 라고 물을수도 있지요. 여기서 빅오? 라는 것은 O(N)을 뜻하는데.
O는 빅오의 기호이고 (작업연산 기호), N은 작업 연산량을 뜻합니다. 예를들어
For가 10번 반복을 하고 연산이 10개 있는 곳에서는 O(N)이 되는것이지요.
또한 더 살펴 보자면, 빅오가N2 일경우는 O(N2) 라고 표현하고, 작업연산량이 N의 제곱 만큼 수행시간을 가지는것입니다.
알고리즘 A, B가 있다고 합시다. A , B 알고리즘은 둘 다 1부터 N까지의 합을 구하는 형태라고 정해져 있고
A알고리즘은 x += a; 를 N번 반복하는 함수 형태이며
B알고리즘은 x = N * ( 1 + N) / 2 인 형태일 경우.
A알고리즘은 총 N*2번의 연산을 하지만은 (덧셈을 100번, x변수에 대입을 100번)
B알고리즘은 총 4번의 연산을 하게 됩니다. (덧셈 1번, 곱셈 1번, 나눗셈 1번, 대입 1번)
A - O(2n) 이지만, B - O(4)=O(1)이 됩니다.
아래는 Big O의 수행 시간에 따른 순서도 입니다. 참조하시길 바랍니다.
비교기준 : 시간 || O(1) < O(log N) < O(N) < O(N log N) < O(N2) < O(N3) < O(2n) < O(n!)
