알고리즘

알고리즘이란 무엇일까?

─────────────────────────────────────

알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다.

또한 알고리즘은 다음과 같은 조건을 만족해야 한다.

1. 입력 : 외부에서 받는 자료의 개수가 0개 이상 존재해야 한다.

2. 출력 : 외부로 출력하는 결과의 값이 적어도 2개이상 존재해야 한다.

3. 명확성 : 알고리즘의 수행과정이 명확하고 애매 모호하지않은 명령들로 구성되어야 한다. 

4. 유한성 : 명령의 개수가 유한해야하고 유한한 시간내에 종료되어야 한다.

5. 효율성 : 모든 알고리즘의 과정은 실행가능해야 한다.

알고리즘에는 복잡도라는 개념이 있다.

복잡도는 알고리즘에서 그 알고리즘이 어느정도 복잡하고 어느정도의 작업량을 가지는지를 알수 있게 해주는 개념이다.

주로 빅오 표기법으로도 부른다.

빅오 표기법 이란?

─────────────────────────────────────

빅오 표기법 이란 프로그램의 복잡도를 시간적으로 표현하는 방법 중 하나이다.

주로 알고리즘의 시간복잡도를 계산하여 알고리즘의 성능을 표현하는데 사용한다.

 

빅오 표기법에는 대표적으로

O(1), O(log N), O(n), O(N log N), O(n^2), O(n^3) 등이 있다.

 

O(1): 상수형 빅-오 표기, 데이터 수에 상관없이 연산의 횟수가 고정 된 형태의 알고리즘

O( log N ): 로그형 빅-오 표기, 데이터 수가 증가율에 비하여 연산횟수의 증가율이 훨씬 적은 형태의 알고리즘

 

O(n): 선형 빅-오 표기, 데이터 수의 증가에 따라 연산횟수가 비례하여 증가한다.

 

O( N log N ): 선형 로그형 빅-오 표기법, 데이터 수가 증가하면 증가되는 연산횟수가

로그형으로 표기한 알고리즘 보다 조금 더 증가하는 알고리즘

 

O(n^2): 데이터수의 제곱에 해당하는 연산횟수를 가진 알고리즘

 

O(n^3): 데이터수의 세제곱에 해당하는 연산횟수를 가진 알고리즘

 

O(n!): 팩토리얼형 빅-오 표기법, 데이터의 수가 증가할수록 연산횟수가 매우 커진다.

▲ 빅오 표기법들의 시간복잡도 그래프

(평평한 표기법일수록 효율이 좋다.)

 

위에서 설명한 빅오 표기법을 시간복잡도 순서로 나열하면 아래와 같다.

(시간복잡도가 적은 순서대로)

 

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

우선 기초적인 내용은 이정도로 설명하고 다음 글 부터는 자료구조에 대해서 설명할것이다.

자료구조의 설명은 여기서 한다.

자료구조란 무엇일까?

─────────────────────────────────────

 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 사용자가 신중하게 선택한 자료구조는 알고리즘의 효율을 향상시키는데 큰 역활을 한다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

자료구조의 종류로는 리스트, 스택, 큐, 트리, 정령, 탐색 등등 매우 많은 자료구조가 있다.

앞으로 자료구조의 종류에 대해서 설명하고 직접 구현하는 과정으로 진행할것이다.