데이터 구조에서 검색: 다양한 검색 방법 설명
게시 됨: 2021-05-03통신망이 확장되어 사람들이 인터넷을 사용하고 있습니다! 기업은 효율적인 관리를 위해 디지털화하고 있습니다. 인터넷에서 생성되는 데이터가 증가함에 따라 데이터 세트가 복잡해지고 있습니다. 데이터를 신중하고 효율적으로 구성, 관리, 액세스 및 분석하는 것이 필수적이며 데이터 구조가 가장 유용한 기술이며 기사에서는 동일한 내용에 중점을 둡니다!
목차
데이터 구조
컴퓨터 과학에서 데이터 구조는 ADT(추상 데이터 유형)의 기초이며, 여기서 ADT는 데이터 유형의 논리적 형식입니다. 데이터 유형의 물리적 레이아웃은 데이터 구조를 사용하여 구현됩니다. 다른 종류의 응용 프로그램에 다른 데이터 구조 유형이 사용됩니다. 일부는 특정 작업에 특화되어 있습니다.
데이터 구조는 데이터 값과 이들 간의 관계, 데이터에 적용할 수 있는 작업 및 기능의 모음입니다. 특정 형식으로 데이터를 구성, 관리 및 저장하는 데 도움이 됩니다. 따라서 사용자는 쉽게 액세스하고 데이터를 효율적으로 수정할 수 있습니다.
데이터 구조는 대용량 데이터베이스와 같은 대용량 데이터를 관리하는 데 도움이 됩니다. 효율적인 알고리즘은 효율적인 데이터 구조를 기반으로 구축됩니다. 효율적인 저장 외에도 데이터 구조는 저장된 메모리에서 정보를 효율적으로 검색하는 역할도 합니다. 여기에는 배열, 연결 목록, 포인터, 검색, 스택, 그래프, 대기열, 구조, 프로그램, 정렬 등이 포함됩니다.
이 기사에서는 데이터 구조에서 검색의 개념과 그 방법을 다룹니다. 개념을 명확하게 이해할 수 있도록 알고리즘의 두 가지 예를 자세히 설명합니다. 추가 지식, 기술 및 전문 지식을 얻기 위해 기사 끝에 언급된 데이터 구조에 대한 온라인 과정을 사용할 수 있습니다.
데이터 구조에서 검색이란 무엇입니까?
컴퓨터 메모리에 있는 요소의 형태로 저장된 항목들의 집합에서 원하는 정보를 찾는 과정을 '자료구조 검색'이라고 한다. 이러한 항목 집합은 배열, 트리, 그래프 또는 연결 목록과 같은 다양한 형태입니다. 데이터 구조에서 검색을 정의하는 또 다른 방법은 항목 모음에서 특정 특성의 원하는 요소를 찾는 것입니다.
검색 방법
데이터 구조에서 검색은 저장된 데이터 구조의 모든 형태에서 요소를 확인하거나 검색하는 검색 알고리즘을 구현하여 수행할 수 있습니다. 이러한 알고리즘은 다음과 같은 검색 작업 유형에 따라 분류됩니다.
- 순차 검색
배열 또는 요소 목록은 집합의 모든 구성 요소를 확인하는 동안 순차적으로 탐색됩니다.
예를 들어 선형 검색.
- 간격 검색
정렬된 데이터 구조에서 검색하도록 명시적으로 설계된 알고리즘은 간격 검색에 포함됩니다. 이러한 알고리즘의 효율성은 선형 검색 알고리즘보다 훨씬 우수합니다.
예를 들어, 이진 검색, 대수 검색.
이러한 방법은 알고리즘이 데이터 컬렉션에서 검색 항목과 일치하는 요소를 검색하는 데 걸리는 시간을 기반으로 검사되며 다음과 같이 제공됩니다.
- 최고의 시간
- 평균 시간
- 최악의 시간
주요 관심사는 알고리즘 성능에 대한 보장된 예측으로 이어지며 평균 시간과 비교하여 계산하기 쉬운 최악의 시간에 관한 것입니다.
이 문서의 예와 개념을 설명하기 위해 모든 데이터 형식의 데이터 컬렉션에 있는 'n' 항목이 고려됩니다. 지배적 연산은 분석 및 알고리즘 비교를 단순화하는 데 사용됩니다. 데이터 구조에서 검색할 때 비교는 O()로 표시되고 "big-Oh" 또는 "Oh"로 발음되는 주요 연산입니다.
선형 탐색, 이진 탐색, 보간 탐색, 점프 탐색, 지수 탐색, 피보나치 탐색, 하위 목록 탐색, 유비쿼터스 이진 탐색, 무한 이진 탐색, 부분 문자열 탐색을 위한 재귀 함수, 재귀 프로그램과 같은 데이터 구조에 수많은 탐색 알고리즘이 있습니다. 주어진 배열에서 요소를 선형으로 검색합니다. 이 기사는 선형 및 이진 검색 알고리즘과 그 작동 원리로 제한됩니다.
데이터 구조의 선형 검색과 이진 검색에 대해 자세히 알아보겠습니다.
선형 검색
선형 검색 알고리즘은 배열의 모든 요소를 순차적으로 검색합니다. 최고의 실행 시간은 1인 반면 최악의 실행 시간은 n입니다. 여기서 n은 검색 배열의 총 항목 수입니다.
데이터 구조에서 가장 간단한 검색 알고리즘이며 데이터 수집이 끝날 때까지 검색 요소와 일치할 때까지 요소 집합의 각 항목을 확인합니다. 데이터가 정렬되지 않은 경우 선형 검색 알고리즘이 선호됩니다.
선형 검색에는 아래와 같은 복잡성이 있습니다.
- 공간 복잡성
선형 탐색의 공간 복잡도는 n이 배열의 요소 수인 추가 공간을 사용하지 않기 때문에 O(n)입니다.
- 시간 복잡도
*최상의 복잡도 = O(1)은 검색 요소가 검색 배열의 첫 번째 요소에 있을 때 발생합니다.
*최악의 복잡도 = O(n)은 검색 요소가 요소 집합이나 배열에 존재하지 않을 때 발생합니다.
*평균 복잡도 = O(n)은 요소가 검색 배열의 어딘가에 존재할 때 참조됩니다.
예시,
아래와 같이 요소의 배열을 취합시다.
45, 78, 12, 67, 08, 51, 39, 26
위에 주어진 8개 요소의 배열에서 '51'을 찾기 위해 선형 검색 알고리즘은 포인터가 메모리 공간에서 51을 가리킬 때까지 각 요소를 순차적으로 검사합니다. 배열에서 51을 찾는 데 O(6) 시간이 걸립니다. 위의 배열에서 12를 찾으려면 O(3)이 필요하지만 26의 경우 O(8) 시간이 필요합니다.
이진 검색
이 알고리즘은 데이터 수집에서 가장 중간에 있는 항목을 비교하여 특정 항목을 찾습니다. 일치가 발생하면 항목의 인덱스를 반환합니다. 중간 항목이 항목보다 크면 왼쪽 하위 배열의 중심 항목을 찾습니다. 반대로 중간 항목이 검색 항목보다 작으면 오른쪽 하위 배열에서 항목의 중간을 탐색합니다. 항목을 찾거나 하위 배열 크기가 0이 될 때까지 항목을 계속 검색합니다.
이진 검색에는 항목의 정렬된 순서가 필요합니다. 선형 검색 알고리즘보다 빠릅니다. 분할 정복 원칙에 따라 작동합니다.
런타임 복잡도 = O(log n)
이진 검색 알고리즘은 다음과 같이 복잡합니다.
- 최악의 경우 복잡도 = O(n log n)
- 평균 복잡도 = O(n log n)
- 최상의 경우 복잡도 = O(1)
예시,
08개 요소로 구성된 정렬된 알고리즘을 살펴보겠습니다.
08, 12, 26, 39, 45, 51, 67, 78
위 요소의 배열에서 51을 찾으려면
알고리즘은 배열을 08, 12, 26, 39 및 45, 51, 67, 78의 두 배열로 나눕니다.
51은 39보다 크므로 배열의 오른쪽에서 요소 검색을 시작합니다.
45, 51 및 67, 78과 같이 두 개로 더 나뉩니다.
51은 67보다 작으므로 해당 하위 배열의 왼쪽에서 검색을 시작합니다.
그 하위 배열은 다시 45와 51로 두 개로 나뉩니다.
51은 검색 요소와 일치하는 숫자이므로 배열에서 해당 요소의 인덱스 번호를 반환합니다.
검색 요소(51)가 어레이의 6번째 위치에 있다는 결론을 내릴 것입니다.
이진 검색은 비교 횟수가 선형 검색 알고리즘보다 크게 줄어들기 때문에 시간을 절반으로 줄입니다.
읽기: Python의 데이터 구조 유형
보간 검색
이진 검색 알고리즘의 향상된 변형이며 검색 요소의 탐색 위치에서 작동합니다. 이진 검색 알고리즘과 유사하게 정렬된 데이터 수집에서만 효율적으로 작동합니다.
최악의 실행 시간 = O(n)
데이터 수집에서 대상 요소의 위치가 알려진 경우 보간 검색이 사용됩니다. 전화 번호부에서 번호를 찾으려면 선형 또는 이진 검색을 사용하는 대신 Monica의 전화 번호를 검색하려는 경우 이름이 'M'으로 시작하는 메모리 공간 저장소를 직접 탐색할 수 있습니다.
결론
데이터 구조에서 검색한다는 것은 'n' 요소의 배열에서 주어진 요소를 찾는 것을 의미합니다. 즉, 두 가지 범주가 있습니다. 검색 시 순차 검색 및 간격 검색. 거의 모든 검색 알고리즘은 이 두 범주 중 하나를 기반으로 합니다. 선형 및 이진 검색은 이진이 선형 알고리즘보다 빠르게 작동하는 간단하고 구현하기 쉬운 두 가지 알고리즘입니다.
선형 검색이 가장 간단하지만 검색 요소와 일치하는 항목을 찾을 때까지 각 요소를 확인하므로 데이터 수집이 올바르게 정렬되지 않은 경우 효율적입니다. 그러나 데이터 수집이 정렬되고 배열의 길이가 상당하면 이진 검색이 더 빠릅니다.
데이터 구조는 데이터 세트를 다루는 동안 컴퓨터 프로그래밍의 필수적인 부분입니다. 프로그래머와 개발자는 컴퓨터 프로그래밍 기술의 기본 및 업데이트를 통해 계속 업데이트하고 기술을 향상시켜야 합니다. 데이터 구조를 다루는 프로그래머는 코스를 자주 선택해야 합니다.
데이터 과학에 대해 자세히 알아보려면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 전문가와의 멘토링, 업계 멘토와의 1:1 학습, 400시간 이상의 학습 및 최고의 기업과의 취업 지원.
