Data Structure and Algorithms (1)

Data Structures

What are data structures?

Data Structures는 데이터를 구성, 저장, 조작하는 방법을 의미합니다.

 

What is Abstract Data Type(ADT)?

복잡한 데이터나 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것입니다.
ADT는 프로그래밍을 함에 있어 데이터를 추상화하여 논리적인 구조를 정의한 것입니다.

 

Time and space complexity

자료구조가 데이터를 얼마나 효율적으로 처리할 수 있도록 도와주는지를 어떻게 평가할 수 있을까요?

• 두가지 평가 요소
• Time Complexity: 프로그램이 실행되고, 완료되는데 걸리는 시간
• Space Complexity: 프로그램이 실행되고 완료되는데 필요한 메모리

Space Complexity는 고정공간 요구량(Fixed space requirements)과 가변공간 요구량(Variable space requirements)을 더해 계산합니다.
Time Complexity는 Compile Time과 Execution Time으로 나뉘는데, 우리는 Execution Time의 complexity만을 계산합니다. (Compile Time은 조절이 불가능합니다!)

 

Best, average, and worst-case analysis

Big Oh, Big Ω, and Big Θ notation
복잡도를 표현하는 방법으로는 Big Oh, Big Ω, and Big Θ notation을 사용합니다.
Big Oh는 최악의 경우(최대로 걸릴 수 있는 상한 시간), Big Ω는 최선의 경우(최소로 걸릴 수 있는 하한 시간), Big Θ는 평균의 경우로 나타냅니다.
보편적으로 big-oh 표기법을 가장 많이 사용합니다.
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < O(2^N) < O(N!) (N : 데이터의 개수)