자료구조 - 복잡도

자료구조(data structure) 이란 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다.

 

시간 복잡도

: 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 효율적인 코드로 개선하는 데 쓰이는 척도가 되기 때문에 필요하다.

 

빅오 표기법

시간 복잡도 표기할 때 가장 많이 사용하는 방법으로, 

복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애 복잡도를 나타내는 표기법이다.

 

ex)

'입력 크기 n '의 모든 입력에 대한 알고리즘에 필요한 시간이 10n² + n 이라고 가정했을 때 이를 빅오표기법으로 나타내면 O(n²) 이 된다. n 의 값이 커질 수록 10n² 의 항이 연산량이 가장 커지고 이에 비해 나머지 항들의 연산량은 적은 편이기 때문에 10n² 에서 상수인자를 제외한 n² 이 된다.

 

 

빅오표기법의 종류로는 O(n!), O(2ⁿ), O(n²), O(n log n), O(1) 가 있으며

O(n!) > O(2ⁿ) > O(n²) > O(n log n) > O(1) 순서로 기억하면 된다.

 

 

공간 복잡도

: 컴퓨터 프로그램을 실행시켰을 때 필요로 하는 자원공간의 양을 말한다. 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로하는 경우 역시 포함된다.

 

공간복잡도의 범위

1. 최대범위를 기반으로 먼저 선언하는 방법

  : n 의 최대범위가 1,000,000 라고 할 때 int a [1000000]; 와 같이 미리 선언하는 방법이다.

 

2. 메모리 제한을 참조하는 방법

  : 메모리의 제한이 512MB 라고 할  때 512 MB = 512,000,000 byte 따라서 int a [128,000,000]; 와 같이 선언하는 방법이다.