[Kotlin] 자료 구조와 알고리즘의 이해

 

 

 

 

 

 

1. 자료구조에 대한 기본적인 이해

 

(1). 자료 구조란 무엇인가?

 

 - 자료구조(Data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 

 - 프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리 하는 것이다.

이 때 데이터를 표현하는 것이 자료구조, 데이터를 처리 하는 것이 알고리즘이다. (때문에 자료 구조와 알고리즘이 항상 같이 붙어 다니는 것!) 

 

ex ) 

 

 

 

 

 

 

- 자료구조의 종류를 나눠보면 아래처럼 나눌 수 있다.

 

 

 

 

 

 

 

(2). 알고리즘의 성능분석 방법

 - 알고리즘을 평가하는 두 가지 요소

• 시간 복잡도 -> 얼마나 빠른가
• 공간 복잡도 -> 얼마나 메모리를 적게 쓰는가

    => 시간 복잡도가 더 중요 ! 

 

 

 

- 시간 복잡도의 평가 방법

• 중심이 되는 특정 연산의 횟수를 세어서 평가한다.
• 데이터의 수에 대한 연산 횟수의 함수를 구한다.

 

 

- 알고리즘의 수행 속도 비교

• 데이터의 수가 적은 경우, 수행 속도는 큰 의미가 없다 때문에 데이테 수에 따른 수행 속도의 변화 정도를 기준으로 한다.
• 최상의 경우 : 배열의 맨 앞에서 대상을 찾는 경우 -> 오메가 표기법 (Big-Ω Notation)
• 평균적인 경우 : 일반적으로 등장하는 상황에 대한 경우 -> 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 배열의 끝에서 찾거나 대상이 저장되지 않은 경우 -> 빅오 표기법 (Big-O Notation)