공간복잡도2 [APS] 003 : 자료구조 개론 자료구조 자료구조(data structure) - 효율적인 관리를 위해 특성이나 상호 관계 등에 따라 구조화시킨 데이터, 혹은 그의 집합체 - 대부분의 프로그래밍 언어는 자료형(data type) 을 통해 자료구조를 정의 원시 자료형 : 자료를 특성에 따라 효율적으로 메모리에 저장하기 위한 단순한 자료구조 추상 자료형(ADT : Abstract Data Structure) 다수의 원시형 자료들을 용도 등에 따라 효율적으로 관리하기 위해 정의된 자료구조 구성하는 원시 자료형과 필요한 연산 등을 수학적/논리적으로 정의해놓은 집합체 ※ 자료구조가 실제적으로 정의된 용어라면, 자료형은 각 프로그래밍 언어에서 정의된 형식이다. 예를 들어 Java 는 인터페이스(혹은 추상클래스)를 통해 특정 자료구조에 대응되는 자.. 2023. 4. 10. [APS] 002. 복잡도 복잡도 복잡도(Complexity) - 알고리즘의 성능을 나타내는 척도로, 점근 표기법 을 사용 - 수행 시간을 의미하는 시간복잡도 와 필요 공간(메모리)를 의미하는 공간복잡도 로 나눔 점근 표기법(Asymptotic notation) - 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수학적 방법 빅오메가(Ω; Big-Omega) : 최선의 경우에도 작아질 수 없는 함수의 집합(하한) 빅오(O; Big-Oh) : 최악의 경우에도 커질 수 없는 함수의 집합(상한) 빅세타(Θ; Big-Theta) : 빅오메가와 빅오를 모두 만족하는 함수의 집합 - 가장 지배적인(dominant) 영향을 주는 최고차항만을 표기하며, 계수는 표기하지 않음 - 알고리즘에서는 최악의 경우를 가정하는 빅오 표기법을 주로 사.. 2023. 4. 10. 이전 1 다음
