1-1) 자료구조의 시작, 복잡성

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

자료구조 (Data structure)

자료에 대한 처리를 효율적으로 수행할 수 있도록 데이터를 표현(조직) 및 저장하는 방법

+ 자료구조에 따라 알고리즘은 달라짐, 즉 알고리즘은 자료구조에 의존적이므로 자료구조와 알고리즘을 함께 말하는 것.

 

 

다루게 될 자료구조의 종류

 

 

연결 리스트(Linked list), 스택&큐(Stack & Queue), 해시(Hash), 트리(Tree), 정렬(Sort)

 

 

시간 복잡도: 서로 다른 알고리즘의 효율성 비교

알고리즘 비교 시 규칙

1.  input  ≥  0

입력값(n)은 시간 복잡도에서 음수일 수 없기에, 항상 0보다 크다고 가정한다.

 

2. functions do more work for more input

함수는 더 많은 입력값이 주어지면 더 많은 작업을 한다. 입력 값이 많으면 작업 시 필요한 계산이나 처리 시간이 길어진다.

 

3. drop all constants

시간 복잡도에서는 모든 상수는 고려하지 않는다.(무시된다) 

ex) 2n, 3n, 10n은 모두 복잡도가 n인 알고리즘(n이 무한으로 커질 때 미미한 차이)

 

4. ignore lower order terms

낮은 차수의 항들은 무시한다. (+ n의 값으로 1 이하는 고려하지 않는다.) n과 n^2를 비교할 때 n^2가 항상 더 오래 걸림

ex) 입력값 n이 무한이 될 때 n^3​​+n^​2​​+n 에서 뒤의 차수는 시간 복잡도에 영향 X. n^3만 고려 

 

5. ignore the base of logs

로그의 밑은 무시한다. 로그들은 서로 배수이기에 비교할 때 밑은 고려하지 않고, 'log n 복잡도를 가진다'고 표현한다.

 

6. 2n = O(n) =>  2n ∈ O(n)

'2n은 O(n)이라는 함수의 집합에 속한다. '  즉, 2n = O(n)에서 등호는 집합에 속한다는 뜻이다.

 

 

시간복잡도 예

1, C  - 상수 시간 (constant time). n과 독립적

log n - 일반적으로 트리

n - 각각의 요소마다 한 번씩 작업할 때. 연결 리스트 탐색n^2 - 모든 요소를 서로 비교하는 경우. 버블 정렬(비효율적..)

n! - 외판원 문제(TSP: Traveling Salesman Problem)

 

 

생각해보기

Q. 시간 복잡도가 1이거나 n인 것은 각각 무엇을 의미할까?

A. 시간 복잡도가 1인 것은 입력값과 독립적으로 일정한 시간이 소요되는 경우이며, 시간 복잡도가 n인 것은 입력 값에 비례하여 시간이 소요되는 경우를 의미할 것이다.

 

 

comment

정처기 필기를 준비하며 외우기만 했던 정렬의 시간 복잡도, 무얼 뜻하는 지 대략 이해하게 되었다.