데이터 구조 및 알고리즘-개요
데이터 구조는 데이터를 효율적으로 사용하기 위해 데이터를 체계적으로 구성하는 방법입니다. 다음 용어는 데이터 구조의 기본 용어입니다.
Interface− 각 데이터 구조에는 인터페이스가 있습니다. 인터페이스는 데이터 구조가 지원하는 일련의 작업을 나타냅니다. 인터페이스는 지원되는 작업 목록, 허용 할 수있는 매개 변수 유형 및 이러한 작업의 유형을 반환하기 만합니다.
Implementation− 구현은 데이터 구조의 내부 표현을 제공합니다. 구현은 또한 데이터 구조의 작업에 사용되는 알고리즘의 정의를 제공합니다.
데이터 구조의 특성
Correctness − 데이터 구조 구현은 인터페이스를 올바르게 구현해야합니다.
Time Complexity − 데이터 구조 작업의 실행 시간 또는 실행 시간은 가능한 한 작아야합니다.
Space Complexity − 데이터 구조 연산의 메모리 사용량은 가능한 한 적어야합니다.
데이터 구조의 필요성
애플리케이션이 복잡해지고 데이터가 풍부 해짐에 따라 오늘날 애플리케이션이 직면하는 세 가지 일반적인 문제가 있습니다.
Data Search− 한 상점 에서 1 백만 (10 6 ) 품목의 재고를 고려하십시오 . 애플리케이션이 항목을 검색하는 경우 검색 속도를 늦출 때마다 100 만 (10 6 ) 항목의 항목을 검색해야합니다. 데이터가 증가하면 검색 속도가 느려집니다.
Processor speed − 프로세서 속도는 매우 높지만 데이터가 10 억 개의 레코드로 증가하면 제한됩니다.
Multiple requests − 수천 명의 사용자가 웹 서버에서 동시에 데이터를 검색 할 수 있기 때문에 빠른 서버에서도 데이터를 검색하는 동안 실패합니다.
위에서 언급 한 문제를 해결하기 위해 데이터 구조가 구출됩니다. 모든 항목을 검색 할 필요가없고 필요한 데이터를 거의 즉시 검색 할 수있는 방식으로 데이터를 데이터 구조로 구성 할 수 있습니다.
실행 시간 사례
다양한 데이터 구조의 실행 시간을 상대적으로 비교하는 데 일반적으로 사용되는 세 가지 경우가 있습니다.
Worst Case− 특정 데이터 구조 작업에 최대 시간이 걸리는 시나리오입니다. 작업의 최악의 경우 시간이 ƒ (n)이면이 작업은 ƒ (n) 시간 이상 걸리지 않습니다. 여기서 ƒ (n)은 n의 함수를 나타냅니다.
Average Case− 이것은 데이터 구조 작업의 평균 실행 시간을 나타내는 시나리오입니다. 작업 실행에 ƒ (n) 시간이 걸리면 m 작업이 mƒ (n) 시간이 걸립니다.
Best Case− 이것은 데이터 구조 작업의 가능한 최소 실행 시간을 묘사 한 시나리오입니다. 작업 실행에 ƒ (n) 시간이 걸리면 실제 작업에 최대 ƒ (n)이되는 난수로 시간이 걸릴 수 있습니다.
기본 용어
Data − 데이터는 값 또는 값 집합입니다.
Data Item − 데이터 항목은 단일 값 단위를 나타냅니다.
Group Items − 하위 항목으로 구분 된 데이터 항목을 그룹 항목이라고합니다.
Elementary Items − 나눌 수없는 데이터 항목을 기본 항목이라고합니다.
Attribute and Entity − 엔티티는 값이 할당 될 수있는 특정 속성 또는 속성을 포함하는 것입니다.
Entity Set − 유사한 속성의 엔티티는 엔티티 세트를 형성합니다.
Field − 필드는 엔티티의 속성을 나타내는 단일 기본 정보 단위입니다.
Record − 레코드는 주어진 엔티티의 필드 값 모음입니다.
File − 파일은 주어진 엔티티 세트에있는 엔티티의 레코드 모음입니다.