[알고리즘] 알고리즘의 개념과 성능 분석(시간 복잡도, 빅-오 표기법)

알고리즘과 자료구조

• 알고리즘=어떤 문제를 해결해가는 논리적인 과정
• 데이터와 그 데이터를 처리하는 방법의 관계
• 자료구조) 효율적 접근과 수정이 가능하도록 자료를 구성, 관리, 저장하는 것
• 알고리즘) 어떤 문제를 해결하기 위해 정해진 일련의 단계적인 절차나 방법

 

알고리즘 표현법

 

일반 언어 표현

• 일반적인 자연어를 사용해서 설명하듯이 표현

순서도 (flowchart) 를 이용한 표현

• 순서도(flowchart)란 어떠한 일을 처리하는 과정을 순서대로 간단한 기호와 도형으로 도식화한 것을 의미한다.

의사코드(Pseudo code)를 이용한 표현

• 의사코드 → 프로그램 언어와 일반 언어의 중간 형태
• 정해진 문법이 없어서 자유롭게 작성한다.

프로그래밍 언어로 바로 작성

 

혼합 형태

• 간단한 알고리즘은 바로 프로그래밍 언어로, 복잡한 건 의사코드, 순서도 등을 종합적으로 활용

 

알고리즘의 성능 분석

• 알고리즘의 성능 분석에는 시간 복잡도(time complexity)와 알고리즘이 사용하는 기억 공간을 분석하는 공간 복잡도(space complexity)가 존재한다.
• 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도: 알고리즘을 위해 필요한 메모리의 크기

그러나 알고리즘의 복잡도를 이야기할 때 대게는 시간 복잡도를 말한다.(알고리즘이 차지하는 공간보다는 실행시간에 더 화두를 둔다.)

 

시간 복잡도

• 알고리즘이 이루고 있는 연산들이 입력 개수에 따라 몇번이나 실행되는지를 표시한다.
• 입력 개수가 많아질수록 A<B<C 순으로 연산 횟수가 많아지므로 C의 성능이 떨어진다.
• 알고리즘 A와 같은 것은 실제로 잘 존재하지 않는다.

 

빅-오 표기법

• 가장 많이 사용하는 알고리즘의 성능 표기법이다.
• 가장 높은 항만 표기하고 계수는 생략한다. (자료의 개수가 많아질수록 차수가 가장 큰 항이 큰 영향을 미치고, 다른 항들은 상대적으로 무시 가능하기 때문이다.

• 정확한 연산 횟수를 위한 것이 아니라, 대략적인 시간 측정을 위한 것이다.
• 빅오는 함수의 상한을 표시한다.

 

빅-오 표기법의 대표적인 함수

• 밑에서부터 상수형, 로그형, 선형, 로그선형, 2차형, 지수형 순
• 그 위에 팩토리얼형도 있음

 

• 성능이 좋지 않은 알고리즘일수록 데이터 개수에 따라서 연산 수가 가파르게 증가한다.

 

빅-오메가 표기법 Ω(N)

• 함수의 하한을 표기
• f(n) ≥ Ω(g(n)) 함수 f의 증가속도가 g보다 느리지 않다.
• 어떤 알고리즘의 시간 복잡도가 Ω(f(n))이라면 알고리즘 수행에는 적어도 f(n)의 수행 시간이 필요함을 의미한다.

=> Ω(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 큰 함수의 집합

 

 

빅-세타 표기법 Θ(N)

• 함수의 하한인 동시에 상한을 표시
• f(n) = θ(g(n)) 함수 f의 증가속도가 g랑 비슷하다.
• 최고차항의 차수가 g(n)과 일치하는 함수의 집합이다.