(Data Structure) 자료구조,알고리즘

자료구조 예습 #1

• 요즘 도서관에서 이것저것 찾아보는데 재미가 들렸다. 다음 학기에 자료구조를 배우게 되는데, 이번에 예습을 간단히라도 해봐야겠다.

자료구조 (Data Structure)

전산학에서는 컴퓨터에 의한 자료의 표현, 변형을 할때 자료의 형태 및 동작 유형을 고려하여 효과적으로 동작을 수행할 수 있게 하는 표현기법을 연구하는데,
여기에 사용되는 자료의 형태, 유형 등을 자료구조라고 한다.

이때 자료를 여러 형태로 표현, 처리하는 방법을 알고리즘 (Algorithm) 이라고 한다.

자료구조와 알고리즘은 상호 협조의 관계이다.

알고리즘 (Algorithm)

이번 학기에 배우는 것은 알고리즘이 아닌 자료구조 이지만, 두가지가 밀접한 관계인만큼 결국엔 같이 배워 나가게 되지 않을까 싶다.

알고리즘은 특별한 일을 수행하는 명령어들의 유한 집

• 알고리즘의 조건
  1. 입력(input) : 입력받는 자료는 0개 이상이다.
  2. 출력 (output) : 생성되는 결과는 적어도 한가지 이상이다.
  3. 명확성 (definiteness) : 각 명령은 명백해야 하고 모호하지 않아야한다.
  4. 유한성 (finiteness) : 명령대로 수행한 뒤, 일정한 수의 단계 후에는 반드시 종료되어야 한다.
  5. 효과성 (effectiveness) : 반드시 실행가능해야 한다. (말로만 되는건 X)

알고리즘 분석

알고리즘을 분석함으로써 알고리즘의 실행 시간을 확인하고 더 빠른 시간에, 효율적으로 수행이 가능한 알고리즘을 택하는데 목적이 있다.

시간 복잡도 (time complexity)

공간 복잡도 (space complexity)

를 이용해 알고리즘을 분석한다.

알고리즘의 시간 복잡도를 측정하기 위해서는 알고리즘의 총 계산 단계수를 구해야 한다.

계산 단계수는 알고리즘 내에서의 수행 빈도수를 합한 것이다.

알고리즘 내에서 실행문 하나가 단계수 하나가 되는 것이다.

ex)

x = x + 1;  //단계 수 = 1

-> 총 단계 수 = 1

for (i = 0; i < n; i++) //단계 수 = n+1
	x = x + 1;          //단계 수 = n

-> 총 단계 수 = 2n + 1

for (i = 0; i < n; i++) //단계 수 = n+1
	for (j = 0; j < n; j++) //단계 수 = n(n+1)
		x = x + 1;      //단계 수 = n^2

-> 총 단계 수 = 2n^2 + 2n + 1

x = x + 1;   //단계 수 = 1
for (i = 0; i < n; i++) //단계 수 = n+1
	x = x + 1;   //단계 수 = n
for (i = 0; i < n; i++)  //단계 수 = n+1
	for (j = 0; j < n; j++)  //단계 수 = n(n+1)
		x = x + 1;  //단계 수 = n^2

-> 총 단계 수 = 2n^2 + 4n + 3

이와 같이 단계 수를 구하는 것을 토대로 몇가지 방법을 통해 알고리즘의 시간 복잡도 를 나타낼 수 있다.