자료구조 기초 개념 (Data Structure) (빅오표기법)

자료구조란

프로그램은 데이터의 표현 및 데이터의 처리이다. 이때 데이터의표현은 데이터의 저장을 포함하는 개념이며, 데이터의 저장을 담당하는 것이 자료구조 이다. 

자료구조의 종류는 선형구조(리스트, 스택, 큐), 비선형구조(트리, 그래프), 파일구조, 단순구조가 있다.

---

알고리즘의 성능분석방법 

자료구조와 알고리즘의 정상적인 동작외에 좋은성능인지 알기위하여 자료구조와 알고리즘을 분석하고 평가하기위해서 필요하며, 처리해야할 데이터의수(n)이 있다고 가정했을때 n의 증가에 따라서 변하는 연산횟수로 판단할수 있다.

시간복잡도(time complexity): 알고리즘의 수행시간 분석결과

공간복잡도(space complexity): 메모리 사용량에 대한 분석결과

알고리즘의 동작을 판단할때 최선의 경우(best case)와 최악의 경우(worst case)가 생길수있다. 이때 알고리즘의 성능을 판단하기 위해서 중요한 것은 최악의경우이다. 왜냐하면 대부분의 알고리즘에서 최선의경우는 만족할만한 결과를 보여주기 때문이다.

빅오표기법 (Big Oh Notation)

빅오표기법에서 빅오란 함수 T(n)에서 가장 영향력이 큰 부분을 판단하는것으로 빅오표기법은 알고리즘의 성능을 판단하는 수식을 간략화 해주며, 데이터수의 증가에 따른 연산횟수의 증가패턴을 보여주는 표기법이다.

빅오구하는법: T(n)이 다항식으로 표현된 경우에 최고차항의 차수가 빅오이다. 왜냐하면 다항식으로 표현된 시간복잡도 함수 T(n)에서 가장 큰 영향을 미치는것이 최고차항의 차수 이기 때문이다.

ex) T(n) = n^2 + 2n + 9 -> O(n^2)

ex2) T(n) = 5n^3 + 3n^2 +2n + 1 -> O(n^3)

빅오표기의 대표적인 예

O(1): 상수형 빅오로서 데이터수의 영향을 받지않고 연산횟수가 고정인 알고리즘이다. 

O(log n): 로그형 빅오로서 데이터수의 증가율과 비교했을때 ㅑ8연산횟수의 증가율이 상당히 낮은 알고리즘이다.

O(n): 선형 빅오로서 데이터의수와 연삿횟수가 비례한 알고리즘이다.

O(n log n): 선형로그형 빅오로서 데이터의 수가 두배로 늘어난경우 연산횟수는 두 배를 조그넘게 늘어나는 알고리즘이다.

 

참고: 윤성우의 열혈 자료구조