선형 검색: Python, C++ 예시
검색 알고리즘이란 무엇인가요?
검색 알고리즘은 주어진 데이터 구조를 가진 요소 또는 객체의 컬렉션에서 요소 또는 객체를 찾도록 설계되었습니다. 예를 들어, 주어진 높이 목록에서 최소 높이를 검색하거나 숫자 목록 또는 배열에서 가장 높은 점수를 검색합니다. 몇 가지 인기 있는 검색 알고리즘에는 "선형 검색", "이진 검색", "점프 검색", "피보나치 검색" 등이 있습니다.
선형 검색이란 무엇입니까?
선형 검색은 가장 간단한 검색 알고리즘 중 하나입니다. 주어진 목록이나 배열에서 주어진 요소를 하나씩 검색합니다. 선형 검색은 전체 목록을 반복하고 특정 요소가 검색 요소와 같은지 확인합니다. 선형 검색이라고도 합니다. 순차 검색.
선형 검색 기능은 무엇을 합니까?
정수 배열은 "Numbers,” 변수 “item”에는 검색할 정수가 포함됩니다.
이제 선형 검색 알고리즘은 다음과 같은 출력을 제공할 수 있습니다.
- "-1"; 이는 주어진 요소가 배열에서 발견되지 않음을 의미합니다.
- 0에서 n-1 사이의 숫자; 이는 검색 요소를 찾았으며 배열에 있는 요소의 인덱스를 반환한다는 의미입니다. 여기서 n은 배열의 크기를 나타냅니다.
선형 검색은 어떻게 작동하나요?
정수를 포함하는 배열을 가정해 보겠습니다. 작업은 배열에서 주어진 숫자를 찾는 것입니다.
- 숫자가 배열에 있으면 해당 숫자의 인덱스를 반환해야 합니다.
- 주어진 숫자를 찾을 수 없으면 -1을 반환합니다.
순서도에서 “Data”는 정수 배열이고, “N”은 배열의 크기, “item”은 배열에서 검색하려는 숫자입니다.
선형 검색 알고리즘의 흐름도:
순서도의 단계는 다음과 같습니다.
단계 1) 검색항목 'item'을 읽어보세요.
단계 2) i=0 및 index=-1 시작
단계 3) 만약 내가
단계 4) Data[i]가 "item"과 같으면 5단계로 이동합니다. 그렇지 않으면 6단계로 이동합니다.
단계 5) 인덱스 = i(항목이 인덱스 번호 i에서 발견됨) 8단계로 이동합니다.
단계 6) 나는 = 나는 +1이다.
단계 7) 3 단계로 이동합니다.
단계 8) 중지합니다.
단순화를 위해 정수 배열의 예를 제공합니다. 선형 검색은 문자열, 객체 배열 또는 구조체에도 적용 가능합니다.
순차 검색 알고리즘을 위한 의사 코드
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ 코드 예 선형 검색
#include < bits / stdc++.h > using namespace std; int linearSearch(int * arr, int item, int n) { int idx = -1; for (int i = 0; i < n; i++) { if (arr[i] == item) { idx = i; break; } } return idx; } int main() { int array[] = { 1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10 }; int n = sizeof(array) / sizeof(arr[0]); int item; cout << "Enter a number to search: "; cin >> item; int idx = linearSearch(arr, item, n); if (idx >= 0) { cout << item << " is found at index " << idx << endl; } else { cout << "Could not find " << item << " in the array" << endl; } }
출력:
Enter a number to search: -10 -10 is found at index 14
Python 코드 예 선형 검색
def linearSearch(data, item): for i in range(len(data)): if data[i] == item: return i return -1 data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10] item = int(input("Enter a number to search: ")) idx = linearSearch(data, item) if idx >= 0: print("{} is found at index {}".format(item, idx)) else : print("{} was not found".format(item))
출력:
Enter a number to search: -10 -10 is found at index 14
선형 탐색 알고리즘의 복잡도 분석
일반적으로 시간 복잡도는 특정 작업을 수행하는 데 걸리는 CPU 시간을 의미합니다. 선형 검색 알고리즘에서 작업은 배열의 요소에서 검색 키를 찾는 것입니다.
시간 복잡도에는 세 가지 유형이 있습니다.
- 최악의 시나리오
- 최고의 사례 시나리오
- 평균 사례 시나리오
최악의 시나리오에서 선형 검색의 시간 복잡도:
예를 들어, 크기가 "n"인 배열에서 선형 검색을 수행해야 한다고 가정해 보겠습니다. 인덱스 0부터 n-1 사이에서 검색 항목을 찾을 수 있습니다. 최악의 경우 알고리즘은 배열의 모든 요소를 검색 요소와 일치시키려고 시도합니다.
이 경우 최악의 복잡도는 O(n)이 됩니다. 여기서 “O”-big O Notation은 복잡도 함수를 의미합니다.
최고의 시나리오에서 선형 검색의 시간 복잡도:
배열의 첫 번째 위치에 있는 요소를 검색한다고 가정해 보겠습니다. 이 시나리오에서 선형 검색 알고리즘은 배열의 모든 n개 요소를 검색하지 않습니다. 따라서 복잡도는 O(1)이 됩니다. 즉, 상수 시간입니다.
평균적인 경우의 선형 검색의 시간 복잡도:
배열의 중간 인덱스에서 요소가 발견되면 선형 검색에 대한 평균 케이스 복잡도는 O(N)이라고 할 수 있습니다. 여기서 N은 배열의 길이를 의미합니다.
선형 탐색 알고리즘의 공간 복잡도
선형 검색의 공간 복잡도는 항상 O(N)입니다. 선형 검색 함수에서 어떠한 종류의 임시 변수도 저장하거나 사용할 필요가 없기 때문입니다.
선형 검색 알고리즘을 개선하는 방법
검색은 프로그램 수명 주기 내내 여러 번 수행될 수 있습니다. 선형 검색 알고리즘을 실행하고 특정 키를 여러 번 검색하는 것도 가능합니다. "이진 검색 알고리즘” 배열이 정렬된 배열인 경우.
배열이 10개의 숫자로 구성되어 있고 대상 요소가 5000번째 인덱스에서 발견된다고 가정합니다. 따라서 알고리즘은 5000개의 요소를 비교하려고 합니다. 이제 비교는 CPU에 많은 부담을 주는 작업입니다. 선형 검색 알고리즘을 최적화하기 위해 두 가지 옵션이 있습니다.
- 전치
- 앞으로 이동
전치:
이 방법에서는 검색 요소를 배열의 이전 요소와 교환합니다. 예를 들어, 다음과 같은 배열이 있다고 가정해 보겠습니다.
데이터[] = {1,5,9,8,7,3,4,11}
이제 검색을 하려고 합니다. 4. Steps of Transposition:
단계 1) "4"는 인덱스 6에 있습니다. XNUMX번의 비교가 필요했습니다.
단계 2) 데이터[6]와 데이터[5]를 교환합니다. 그러면 데이터 배열은 다음과 같습니다.
데이터[] = {1,5,9,8,7,4,3,11}
단계 3) 4를 다시 검색하세요. 인덱스 5에서 찾았습니다. 이번에는 XNUMX번의 비교가 필요했습니다.
단계 4) 데이터[5]와 데이터[4]를 교환합니다. 그러면 데이터 배열은 다음과 같습니다.
데이터 [] = {1,5,9,8,4,7,3,11}
이제 알다시피 키가 더 자주 검색될수록 인덱스가 더 많이 감소합니다. 따라서 비교 횟수가 줄어 듭니다.
앞으로 이동:
이 방법에서는 0번째 인덱스의 검색 요소를 교체합니다. 다시 검색하면 O(1) 시간에 찾을 수 있기 때문입니다.
선형 검색 알고리즘 적용
다음은 우리가 사용할 수 있는 몇 가지 선형 검색 애플리케이션입니다.
- 작은 크기의 배열이나 목록의 요소 수가 적은 경우 선형 검색을 사용하는 것이 더 쉽습니다.
- 선형 검색 방법은 단일 또는 다차원 배열 또는 다른 데이터 구조.
- 일반적으로 선형 검색은 "순서가 지정되지 않은" 데이터에서 검색을 수행하는 데 간단하고 효율적입니다. 주어진 정렬되지 않은 목록에서 단일 데이터를 쉽게 가져올 수 있습니다.