[자료구조] 자료구조의 개요

자료구조란?

대량의 데이터를 효과적으로 저장, 처리하는 방법

 

기본적인 자료구조

1. 선형구조

   • 배열

   • 연결 리스트

   • 스택

   • 큐

2. 비선형 구조

   • 트리

   • 그래프

 

알고리즘이란?

어떤 문제를 풀기 위한 절차, 방법

 

자료구조와 알고리즘

서로 필요충분조건이다.

효율적인 자료구조 설계를 위해서는 알고리즘 지식이 필요 ↔ 효율적인 알고리즘을 작성하기 위해서는 문제 상황에 맞는 적절한 자료구조 사용해야 함

 

프로그램의 성능 측정 방법론

• 시간 복잡도(Time Complexity) : 알고리즘에 사용되는 연산 횟수를 의미
• 공간 복잡도(Space Complexity) : 알고리즘에 사용되는 메모리 양
• 수행 시간
  최상 : 오메가 표기법 (Big-Ω Notation)
  평균 : 세타 표기법 (Big-θ Notation)
  최악 : 빅오 표기법 (Big-O Notation)

 일반적으로 시간과 공간은 반비례적인 경향을 가지나, 최근에는 용량이 문제 되는 경우는 크게 없어 시간 복잡도가 우선시된다.

 수행 시간 기준 중 주로 사용하는 것은 최악의 수행 시간이나 수행 시간의 기대치이며, 두 기준은 거의 동일하기 때문에 구분되지 않고 사용하는 경우가 많다.

 

시간 복잡도(Time Complexity)

알고리즘에 사용되는 연산 횟수

최악의 경우를 나타내는 Big-O표기법을 사용

O(3n^2 + n ) = O(n^2)

어차피 n이 무한정 커질 경우 상수는 무시할 수 있기 때문에 시간 복잡도를 표기할 때는 항상 큰 항과 계수만 표시한다.

// O(n)
int main(void)
{
	int a,b;
	cin >> a>> b;
	int sum = 1;
	for(int i=0; i<b ;i++)
	{
		sum *= a;
	}
	cout << sum;
}

// O(n^2)
int main(void)
{
	int n;
	cin >> n;
	for(int i=0; i<n ;i++)
	{
		for( int j=0; j<=i; j++)
		{
			cout<< "*";
		}
		cout << '\n';
	}
}

 

공간 복잡도(Space Complexity)

알고리즘에 사용되는 메모리 양

공간 복잡도를 표기할 때는 일반적으로 MB단위로 표기

int a[1000] : 4KB
int a[1000000] : 4MB
int a[2000][2000] : 16MB

결과
int형 변수는 4byte만큼의 공간을 차지 하기 때문에 int형 변수가 1000개 들어가는 공간 -> 4KB
2차원 변수로 2000*2000*4 => 16MB

8bit → 1byte
1000byte → 1KB
1000KB → 1MB
1000MB → 1GB