자료 구조와 알고리즘

목차: 자료구조와 알고리즘

알고리즘의 성능 분석

-시간/공간 복잡도 분석

-빅오(O)표기법

 

컴퓨터과학과에 복수전공을 하게되어 C언어를 복습할겸 부족했던 지식을 쌓기위해 컴퓨터 분야에서 필수적으로 불리는 과목인 자료구조 수업을 듣게 되었다. 첫날이라 금방 끝나겠지라고 생각했지만 첫날부터 풀강을 하셨다...

 

본론으로 들어가서....

 

자료구조와 알고리즘의 차이에 대해서 잘 모르는 사람이많은데 정확한 정의를 알고 가야지 앞으로 배울 단원에 대해서 헷갈리지 않게된다.

 

자료구조란? -위키백과

자료구조는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

 

알고리즘이란? -위키백과

알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다. 수학과 컴퓨터 과학에서 알고리즘이란 작동이 일어나게 하는 내재하는 단계적 집합이다. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다.

 

무슨 말인지 이해가가는가?

 

즉, 쉽게말해 자료구조란 주기억장치에 자료(데이터)를 어떠한 형태로 저장시킬것인지 결정하는것이다. 

예를들자면 책을 쭉 쌓아놓을지 연도순 또는 "가나다"순으로 정리할지 등등 데이터가 어떠한 형태로 저장되는지 결정하는것이 자료구조이다.

 

자료구조의 종류에는 스택(물건을 쌓아놓는 형태), 큐(매표소의 줄), 리스트(할 일 리스트), 사전, 탐색구조(영어사전), 그래프(지도), 트리(조직도) 등이 있다

 

알고리즘이란 자료(데이터)를 어떠한 형태로 처리(저장, 변형, 수정) 할 것인지를 결정하는것이다. 

예를들자면 정렬된 책을 무작위로 읽을지 왼쪽부터 차례로 읽을지 위에서부터 읽을지 밑에서부터 읽을지 결정하는 것이 알고리즘이다.

 

 

알고리즘을 구현하다보면 EX)(최댓값 구하기) A라는 알고리즘은 연산횟수가 20회이고 B라는 알고리즘은 연산횟수가 50회라면 당연히 어느 알고리즘이 더 효율적이겠는가?

당연히 A알고리즘이다. 이러한 효율적인 알고리즘을 선택하기 위해 제시된게 "시간 복잡도 함수"이다. 시간복잡도 함수란 알고리즘의 실행시간이 아닌 연산 횟수이다. 실행시간은 컴퓨터 성능에 따라 달라지기 때문이다..

 

 

예를들어 양의 정수 N을 N번 더하는 문제가 있다고 생각하자.

 

알고리즘 A	알고리즘 B	알고리즘 C
SUM=N*N	SUM=0 for i=0; i<n; i++ SUM=SUM+n;	for i=0; i<n; i++    for j=0; j<n; j++  SUM=SUM+1

 

	알고리즘 A	알고리즘 B	알고리즘 C
대입 연산	1	n+1	n*n+1
덧셈 연산		n	n*n
곱셈 연산	1
나눗셈 연산
전체 연산 수	2	2n+1	2n^2+1

 

즉 전체 연산수가 가장 적은 A알고리즘이 가장 효율적이다..

 

 

이 순서대로 연산의 횟수가 많아져 시간복잡도가 증가한다.

 

여기서 빅오(O)표기법이란

시간 복잡도를 통해 계산한 연산을 가지고 표현하는 기법인데 최고차항의 계수만 남기고 지수까지도 싹다 버리면됀다 예를들어 3n^2+2n+1 이면 빅요(0)표기법으론 n^2이 돼고, n!+n^2+2^n이면 n!이 됀다.

왜냐하면 n의 갯수가 증가할때마다 n^2의 연산횟수가 대부분을 차지하기 때문이고 점점 큰 알고리즘을 짤때 상세하게 시간복잡도 함수를 구할 수 없기 때문에 대략 빅오(O)표기법을 통해 구한다.