[ C++ ] 자료구조

자료구조

---

1. 자료구조의 필요성

• 데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해할 필요, 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지 발생 가능성

2. 기본적인 자료구조

• 선형 구조
  • 배열
  • 연결 리스트
  • 스택
  • 큐
• 비선형 구조
  • 트리
  • 그래프

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

• 시간복잡도 (Time Complexity) : 알고리즘에 사용되는 연산 횟수를 의미

• 공간복잡도 (Space Complexit) : 알고리즘에 사용되는 메모리의 양을 의미

  효율적인 알고리즘을 사용한다고 가정했을 때 일반적으로 시간과 공간은 반비례 관계, 시간복잡도를 표현할 때, 최악의 경우를 나타내는 Big-O 표기법을 사용

// 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;
}

=> for 문이 한번 쓰였기 때문에 o(n) 의 시간복잡도, for 문이 두번 쓰이면 o(n2) 의 시간복잡도를 가진다.

Int main(void) {

int a, b;

cin >> a >> b;

cout << a+b;

}

=> 이경우는 바로 a+b 가 되기 때문에 시간복잡도는 1 이다.

• 시간복잡도를 표기할 때는 항상 큰 항과 계수만 표시(ex) O(3n2+n) = O(n2))

• N이 무한히 크면 3과 뒤의 n 은 무의미해서 O(n2)로 표기

• 현실의 다양한 문제에서 시간 제한이 1초 정도라고 생각

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