A data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Primitive types – boolean, character, floating-point, integer, enumeration,

Composite types – data types that is built from primitive types and other composite types – array (string), structure (record), union, ...

Abstract data types – list, stack, queue, tree, graph, ...

A data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is separated from the representation of the objects and the implementation of the operations

ADT는 구현 관심x spec만 있음 (어떤 데이터를 받아 어떤 데이터를 리턴하느냐)

Primitive and composite types can also be regarded as a part of ADT

(for example, an array can be viewed as an ADT)

big-O notation

upper bound

We say f(n) = O(g(n)),

iff there exist positive constants c and n0 such that f(n) ≤ c*g(n) for all n, n≥ n0.

– 1 : constant – (log n): logarithmic – (n) : linear – (n^2) : quadratic – (n^3) : cubic – (2^n) : exponential

오메가 : lower bound

세타 : tight bound