알고리즘의 속도를 실시간(초, 분 단위)으로 측정하는 것은 쉽지 않습니다. 한 프로그램이 다른 프로그램보다 느리게 실행될 수 있는 이유는 그 자체의 비효율성 때문이 아니라 운영 체제의 속도 저하, 하드웨어와의 비호환성, 다른 프로세스가 컴퓨터 메모리를 점유하고 있기 때문입니다. 알고리즘의 효율성을 측정하기 위해 보편적인 개념이 고안되었습니다. , 프로그램이 실행되는 환경에 관계없이. 문제의 점근적 복잡성은 Big O 표기법을 사용하여 측정됩니다. f(x)와 g(x)를 x0의 특정 근처에 정의된 함수라고 하고 g는 그곳에서 사라지지 않습니다. 그런 다음 상수 C>가 있는 경우 f는 (x -> x0)에 대해 g보다 "O" 더 큽니다. 0, 점 x0 근처의 모든 x에 대해 부등식이 유지됩니다. |f(x)| <= C |g(x)| 약간 덜 엄격합니다. 상수 C>0이 있는 경우 f는 g보다 "O" 크며, 이는 모든 x > x0에 대해 f(x) <= C*g(x) 두려워하지 마세요. 공식적인 정의! 기본적으로 입력 데이터의 양이 무한대로 증가할 때 프로그램 실행 시간의 점근적 증가를 결정합니다. 예를 들어, 1000개의 요소와 10개의 요소로 구성된 배열을 정렬하는 것을 비교하고 있으며 프로그램의 실행 시간이 어떻게 증가하는지 이해해야 합니다. 또는 문자별로 이동하고 각 문자에 1을 더하여 문자열의 길이를 계산해야 합니다. c - 1 a - 2 t - 3 점근 속도 = O(n), 여기서 n은 단어의 문자 수입니다. 이 원리에 따라 계산하면 전체 줄을 계산하는 데 걸리는 시간은 문자 수에 비례합니다. 20자 문자열의 문자 수를 계산하는 데는 10자 문자열의 문자 수를 계산하는 데 두 배의 시간이 걸립니다. 문자열의 문자 수와 동일한 값을 길이 변수에 저장했다고 상상해 보십시오. 예를 들어 길이 = 1000입니다. 문자열의 길이를 얻으려면 이 변수에만 액세스하면 되며 문자열 자체를 볼 필요도 없습니다. 길이를 어떻게 변경하더라도 항상 이 변수에 액세스할 수 있습니다. 이 경우 점근 속도 = O(1)입니다. 입력 데이터를 변경해도 해당 작업의 속도는 변경되지 않으며 검색은 일정한 시간에 완료됩니다. 이 경우 프로그램은 점근적으로 일정합니다. 단점: 추가 변수를 저장하고 해당 값을 업데이트하는 데 추가 시간을 들여 컴퓨터 메모리를 낭비합니다. 선형 시간이 나쁘다고 생각한다면 훨씬 더 나쁠 수 있다고 확신할 수 있습니다. 예를 들어 O(n 2 )입니다. 이 표기법은 n이 증가함에 따라 요소(또는 다른 작업)를 반복하는 데 필요한 시간이 점점 더 급격하게 증가한다는 것을 의미합니다. 그러나 작은 n의 경우 점근 속도가 O(n 2 )인 알고리즘은 점근 속도가 O(n)인 알고리즘보다 빠르게 작동할 수 있습니다. 그러나 어느 시점에서는 2차 함수가 1차 함수를 추월하게 되며 이를 피할 수 있는 방법이 없습니다. 또 다른 점근적 복잡성은 로그 시간 또는 O(log n)입니다. n이 증가함에 따라 이 함수는 매우 느리게 증가합니다. O(log n)은 정렬된 배열의 고전적인 이진 검색 알고리즘의 실행 시간입니다(강의에서 찢어진 전화번호부를 기억하시나요?). 배열을 2개로 나누고 요소가 위치한 절반을 선택하므로 검색 영역을 절반으로 줄일 때마다 요소를 검색합니다. 처음으로 데이터 배열을 반으로 나누어 찾고 있는 것을 즉시 발견하면 어떻게 될까요? 가장 좋은 시간을 나타내는 용어가 있습니다 - Omega-large 또는 Ω(n). 이진 검색의 경우 = Ω(1)(배열 크기에 관계없이 일정한 시간에 찾습니다). 선형 검색은 검색되는 요소가 첫 번째 요소인 경우 O(n) 및 Ω(1) 시간에 실행됩니다. 또 다른 기호는 세타(Θ(n))입니다. 최선의 선택과 최악의 선택이 같은 경우에 사용됩니다. 이는 문자열의 길이를 별도의 변수에 저장한 예에 적합하므로 길이에 관계없이 이 변수를 참조하는 것으로 충분합니다. 이 알고리즘의 경우 최상의 경우와 최악의 경우는 각각 Ω(1) 및 O(1)입니다. 이는 알고리즘이 Θ(1) 시간에 실행된다는 것을 의미합니다.
선형 검색
웹 브라우저를 열 때 소셜 네트워크에서 페이지, 정보, 친구를 찾으면 매장에서 딱 맞는 신발을 찾을 때와 마찬가지로 검색을 수행하게 됩니다. 아마도 질서정연함이 검색 방법에 큰 영향을 미친다는 사실을 눈치채셨을 것입니다. 옷장에 셔츠가 모두 있다면, 시스템 없이 방 전체에 흩어져 있는 셔츠 중에서 필요한 셔츠를 찾는 것이 일반적으로 더 쉽습니다. 선형 검색은 하나씩 순차적으로 검색하는 방법입니다. Google 검색 결과를 위에서 아래로 검토하면 선형 검색을 사용하는 것입니다. 예 . 숫자 목록이 있다고 가정해 보겠습니다. 2 4 0 5 3 7 8 1 그리고 우리는 0을 찾아야 합니다. 우리는 그것을 즉시 볼 수 있지만 컴퓨터 프로그램은 그런 식으로 작동하지 않습니다. 그녀는 목록의 처음부터 시작하여 숫자 2를 봅니다. 그런 다음 2=0?을 확인합니다. 그렇지 않기 때문에 그녀는 계속해서 두 번째 캐릭터로 넘어갑니다. 거기에서도 실패가 그녀를 기다리고 있으며 세 번째 위치에서만 알고리즘이 필요한 숫자를 찾습니다. 선형 검색을 위한 의사 코드: 선형 검색 함수는 두 개의 인수(키 키와 배열 array[])를 입력으로 받습니다. 키는 원하는 값(이전 예에서는 키 = 0)입니다. 배열은 우리가 원하는 숫자 목록입니다. 살펴보게 됩니다. 아무것도 찾지 못하면 함수는 -1(배열에 존재하지 않는 위치)을 반환합니다. 선형 검색으로 원하는 요소를 찾으면 함수는 배열에서 원하는 요소가 있는 위치를 반환합니다. 선형 검색의 좋은 점은 요소의 순서에 관계없이 모든 배열에 대해 작동한다는 것입니다. 우리는 여전히 전체 배열을 탐색할 것입니다. 이것이 그의 약점이기도 하다. 순서대로 정렬된 200개의 숫자 배열에서 숫자 198을 찾아야 하는 경우 for 루프는 198단계를 거치게 됩니다. 정렬된 배열에 어떤 방법이 더 효과적인지 이미 짐작하셨을 것입니다.
이진 검색과 트리
알파벳순으로 정렬된 디즈니 캐릭터 목록이 있고 미키 마우스를 찾아야 한다고 상상해 보세요. 선형적으로는 시간이 오래 걸릴 것입니다. 그리고 "디렉토리를 반으로 찢는 방법"을 사용하면 Jasmine으로 바로 이동하고 목록의 첫 번째 절반을 안전하게 삭제할 수 있으며 Mickey는 거기에 있을 수 없다는 것을 깨닫게 됩니다. 동일한 원리를 사용하여 두 번째 열을 삭제합니다. 이 전략을 계속하면 몇 단계만 거치면 미키를 찾을 수 있습니다. 숫자 144를 찾으세요. 목록을 반으로 나누고 숫자 13에 도달합니다. 우리가 찾고 있는 숫자가 13보다 큰지 작은지 평가합니다. 13 < 144이므로 왼쪽에 있는 모든 것을 무시할 수 있습니다. 13 그리고 이 숫자 자체. 이제 검색 목록은 다음과 같습니다. 요소 수가 짝수이므로 "중간"(시작 또는 끝에 더 가까움)을 선택하는 원칙을 선택합니다. 우리가 처음에 근접하는 전략을 선택했다고 가정해 보겠습니다. 이 경우 "중간" = 55. 55 < 144입니다. 목록의 왼쪽 절반을 다시 버립니다. 운 좋게도 다음 평균 숫자는 144입니다. 우리는 이진 검색을 사용하여 단 세 단계만으로 13개 요소 배열에서 144를 찾았습니다. 선형 검색은 동일한 상황을 최대 12단계로 처리합니다. 이 알고리즘은 각 단계에서 배열의 요소 수를 절반으로 줄이므로 점근 시간 O(log n)에서 필요한 요소를 찾습니다. 여기서 n은 목록의 요소 수입니다. 즉, 우리의 경우 점근 시간 = O(log 13)(3보다 조금 더 큼)입니다. 이진 검색 함수의 유사 코드: 이 함수는 4개의 인수를 입력으로 사용합니다. 원하는 키, 원하는 키가 있는 데이터 배열 배열 [], min 및 max는 배열의 최대값과 최소값에 대한 포인터입니다. 우리는 알고리즘의 이 단계를 보고 있습니다. 우리의 예에서는 처음에 다음 그림이 제공되었습니다. 코드를 더 분석해 보겠습니다. midpoint는 배열의 중간입니다. 이는 극단점에 따라 달라지며 그 사이의 중심에 위치합니다. 중간을 찾은 후에는 그것이 키 번호보다 작은지 확인합니다. 그렇다면 키는 가운데 왼쪽에 있는 숫자보다 크며 이진 함수를 다시 호출할 수 있습니다. 이제 min = 중간점 + 1입니다. 키 < 중간점으로 판명되면 버릴 수 있습니다. 그 숫자 자체와 그의 오른쪽에 있는 모든 숫자. 그리고 최소 숫자부터 값(중간점 - 1)까지 배열을 통해 이진 검색을 호출합니다. 마지막으로 세 번째 분기: 중간점의 값이 키보다 크지도 작지도 않으면 원하는 숫자가 될 수밖에 없습니다. 이 경우 이를 반환하고 프로그램을 종료합니다. 마지막으로, 찾고 있는 숫자가 배열에 전혀 없는 경우가 발생할 수 있습니다. 이 사례를 고려하기 위해 다음 확인을 수행합니다. 그리고 아무것도 찾지 못했음을 나타내기 위해 (-1)을 반환합니다. 여러분은 이진 검색을 위해서는 배열을 정렬해야 한다는 것을 이미 알고 있습니다. 따라서 특정 요소를 찾아야 하는 정렬되지 않은 배열이 있는 경우 두 가지 옵션이 있습니다.
목록 정렬 및 이진 검색 적용
목록에 요소를 추가하고 제거하는 동시에 목록을 항상 정렬된 상태로 유지하세요.
목록을 정렬된 상태로 유지하는 한 가지 방법은 이진 검색 트리를 사용하는 것입니다. 이진 검색 트리는 다음 요구 사항을 충족하는 데이터 구조입니다.
트리(트리 구조를 에뮬레이트하는 데이터 구조 - 루트와 다른 노드(리프)가 "가지" 또는 주기가 없는 가장자리로 연결되어 있음)입니다.
각 노드에는 0, 1 또는 2개의 하위 항목이 있습니다.
왼쪽 및 오른쪽 하위 트리는 모두 이진 검색 트리입니다.
임의의 노드 X의 왼쪽 하위 트리의 모든 노드는 노드 X 자체의 데이터 키 값보다 작은 데이터 키 값을 갖습니다.
임의의 노드 X의 오른쪽 하위 트리에 있는 모든 노드는 노드 X 자체의 데이터 키 값보다 크거나 같은 데이터 키 값을 갖습니다.
주의: 실제 트리와는 달리 "프로그래머" 트리의 루트가 맨 위에 있습니다. 각 셀을 꼭짓점(Vertex)이라고 하며, 꼭짓점은 모서리(Edge)로 연결됩니다. 트리의 루트는 셀 번호 13입니다. 정점 3의 왼쪽 하위 트리는 아래 그림에서 색상으로 강조 표시됩니다. 우리 트리는 이진 트리에 대한 모든 요구 사항을 충족합니다. 즉, 각 왼쪽 하위 트리에는 정점 값보다 작거나 같은 값만 포함되고, 오른쪽 하위 트리에는 정점 값보다 크거나 같은 값만 포함됩니다. 왼쪽 및 오른쪽 하위 트리는 모두 그 자체가 이진 하위 트리입니다. 이진 트리를 구성하는 방법은 유일한 방법이 아닙니다. 아래 그림에서 동일한 숫자 집합에 대한 다른 옵션을 볼 수 있으며 실제로는 많은 옵션이 있을 수 있습니다. 이 구조는 검색을 수행하는 데 도움이 됩니다. 매번 위에서 왼쪽 및 아래로 이동하여 최소값을 찾습니다. 최대 수를 찾으려면 위에서 아래로 오른쪽으로 이동합니다. 최소값이나 최대값이 아닌 숫자를 찾는 것도 매우 간단합니다. 우리는 정점이 우리가 찾고 있는 정점보다 크거나 작은지에 따라 루트에서 왼쪽이나 오른쪽으로 내려갑니다. 따라서 숫자 89를 찾아야 하는 경우 다음 경로를 따릅니다. 숫자를 정렬 순서로 표시할 수도 있습니다. 예를 들어, 모든 숫자를 오름차순으로 표시해야 하는 경우 왼쪽 하위 트리를 선택하고 가장 왼쪽 꼭지점부터 위로 올라갑니다. 트리에 무언가를 추가하는 것도 쉽습니다. 기억해야 할 가장 중요한 것은 구조입니다. 트리에 값 7을 추가해야 한다고 가정하고 루트로 가서 확인해 보겠습니다. 숫자 7 < 13이므로 왼쪽으로 갑니다. 거기에서 5가 보이고 7 > 5이므로 오른쪽으로 이동합니다. 또한 7 > 8과 8에는 자손이 없으므로 왼쪽 8에서 가지를 만들고 여기에 7을 붙입니다. 또한 정점을 제거할 수도 있습니다 . 그러나 이것은 다소 더 복잡합니다. 고려해야 할 세 가지 삭제 시나리오가 있습니다.
가장 간단한 옵션은 자식이 없는 정점을 삭제해야 한다는 것입니다. 예를 들어 방금 추가한 숫자 7이 있습니다. 이 경우에는 이 숫자가 있는 꼭짓점의 경로를 따라가서 삭제하면 됩니다.
정점에는 하나의 하위 정점이 있습니다. 이 경우 원하는 꼭지점을 삭제할 수 있지만 그 자손은 직계 조상이 성장한 꼭지점인 "할아버지"에 연결되어야 합니다. 예를 들어, 동일한 트리에서 숫자 3을 제거해야 합니다. 이 경우 전체 하위 트리와 함께 해당 하위 트리인 1을 5에 결합합니다. 5의 왼쪽에 있는 모든 꼭지점은 다음과 같으므로 이 작업은 간단하게 수행됩니다. 이 숫자보다 작습니다(그리고 원격 트리플보다 작습니다).
가장 어려운 경우는 삭제되는 정점에 두 개의 자식이 있는 경우입니다. 이제 가장 먼저 해야 할 일은 다음으로 더 큰 값이 숨겨져 있는 꼭지점을 찾아 이를 교환한 다음 원하는 꼭지점을 삭제하는 것입니다. 다음으로 가장 높은 값의 꼭지점은 두 개의 자식을 가질 수 없으며, 왼쪽 자식이 다음 값에 가장 적합한 후보가 됩니다. 트리에서 루트 노드 13을 제거하고 먼저 13에 가장 가깝고 그보다 큰 숫자를 찾습니다. 21입니다. 21과 13을 바꾸고 13을 삭제합니다.
이진 트리를 구축하는 방법에는 여러 가지가 있습니다. 좋은 방법도 있고 좋지 않은 방법도 있습니다. 정렬된 목록에서 이진 트리를 만들려고 하면 어떻게 되나요? 모든 숫자는 이전 숫자의 오른쪽 분기에 추가됩니다. 숫자를 찾고 싶다면 단순히 체인을 따라 내려가는 것 외에는 선택의 여지가 없습니다. 선형 검색보다 낫지 않습니다. 더 복잡한 다른 데이터 구조도 있습니다. 하지만 지금은 고려하지 않겠습니다. 정렬된 목록에서 트리를 구성하는 문제를 해결하기 위해 입력 데이터를 무작위로 혼합할 수 있다고 가정해 보겠습니다.
정렬 알고리즘
숫자 배열이 있습니다. 우리는 그것을 정렬해야 합니다. 단순화를 위해 정수를 오름차순(가장 작은 것부터 큰 것까지)으로 정렬한다고 가정하겠습니다. 이 프로세스를 수행하는 몇 가지 알려진 방법이 있습니다. 또한 언제든지 주제를 구상하고 알고리즘을 수정할 수 있습니다.
선택 항목별 정렬
주요 아이디어는 목록을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누는 것입니다. 알고리즘의 각 단계에서 새 숫자가 정렬되지 않은 부분에서 정렬된 부분으로 이동되는 방식으로 모든 숫자가 정렬된 부분에 포함될 때까지 계속됩니다.
정렬되지 않은 최소값을 찾습니다.
이 값을 정렬되지 않은 첫 번째 값과 교환하여 정렬된 배열의 끝에 배치합니다.
정렬되지 않은 값이 남아 있으면 1단계로 돌아갑니다.
첫 번째 단계에서는 모든 값이 정렬되지 않습니다. 정렬되지 않은 부분을 Unsorted라고 하고, 정렬된 부분을 Sorted라고 부르겠습니다. (이것은 단지 영어 단어이고 Sorted가 "Sorted part"보다 훨씬 짧고 사진에서 더 보기 좋기 때문에 이렇게 합니다.) 배열의 정렬되지 않은 부분(즉, 이 단계에서는 전체 배열에서)에서 최소 숫자를 찾습니다. 이 숫자는 2입니다. 이제 정렬되지 않은 숫자 중 첫 번째 숫자로 변경하고 정렬된 배열의 끝에 넣습니다(이 단계에서는 첫 번째 위치). 이 단계에서는 이것이 배열의 첫 번째 숫자, 즉 3입니다. 2단계. 우리는 숫자 2를 보지 않습니다; 그것은 이미 정렬된 하위 배열에 있습니다. 우리는 두 번째 요소부터 시작하여 최소값을 찾기 시작합니다. 이는 5입니다. 정렬되지 않은 요소 중 3이 최소값이고 정렬되지 않은 요소 중 첫 번째 요소가 5인지 확인합니다. 이들을 교환하고 정렬된 하위 배열에 3을 추가합니다. 세 번째 단계에서는 정렬되지 않은 하위 배열에서 가장 작은 숫자가 4라는 것을 알 수 있습니다. 이를 정렬되지 않은 하위 배열 중 첫 번째 숫자인 5로 변경합니다. 네 번째 단계에서는 정렬되지 않은 배열에서 가장 작은 숫자가 5라는 것을 알 수 있습니다. 6에서 변경하여 정렬된 하위 배열에 추가합니다. 정렬되지 않은 숫자 중 하나의 숫자(가장 큰 숫자)만 남으면 전체 배열이 정렬되었음을 의미합니다! 이것이 코드에서 배열 구현의 모습입니다. 직접 만들어 보세요. 최선의 경우와 최악의 경우 모두 정렬되지 않은 최소 요소를 찾으려면 각 요소를 정렬되지 않은 배열의 각 요소와 비교해야 하며 각 반복마다 이를 수행합니다. 그러나 전체 목록을 볼 필요는 없고 정렬되지 않은 부분만 볼 필요가 있습니다. 이것이 알고리즘의 속도를 변경합니까? 첫 번째 단계에서는 5개 요소 배열에 대해 4번의 비교를 수행합니다. 두 번째에서는 3번, 세 번째에서는 2번입니다. 비교 횟수를 얻으려면 이 숫자를 모두 더해야 합니다. 우리는 합을 얻습니다 . 따라서 최상의 경우와 최악의 경우에서 예상되는 알고리즘 속도는 Θ(n 2 )입니다. 가장 효율적인 알고리즘은 아닙니다! 그러나 교육 목적과 소규모 데이터 세트에는 상당히 적용 가능합니다.
버블정렬
버블 정렬 알고리즘은 가장 간단한 알고리즘 중 하나입니다. 전체 배열을 따라 이동하여 2개의 인접 요소를 비교합니다. 순서가 잘못된 경우 교환합니다. 첫 번째 패스에서는 가장 작은 요소(“float”)가 끝에 표시됩니다(내림차순으로 정렬하는 경우). 이전 단계에서 하나 이상의 교환이 완료된 경우 첫 번째 단계를 반복합니다. 배열을 정렬해 보겠습니다. 1단계: 배열을 살펴봅니다. 알고리즘은 처음 두 요소인 8과 6으로 시작하여 순서가 올바른지 확인합니다. 8 > 6이므로 서로 바꿉니다. 다음으로 두 번째와 세 번째 요소를 살펴보겠습니다. 이제 이들은 8과 4입니다. 같은 이유로 이들을 교체합니다. 세 번째로 8과 2를 비교합니다. 전체적으로 (8, 6), (8, 4), (8, 2) 세 번의 교환을 수행합니다. 값 8은 목록의 올바른 위치에 "부동"되었습니다. 2단계: (6,4)와 (6,2)를 교환합니다. 6은 이제 두 번째 위치에 있으므로 이미 정렬된 목록의 "꼬리"와 비교할 필요가 없습니다. 3단계: 4와 2를 바꿉니다. 4개가 올바른 위치로 "떠오릅니다". 4단계: 배열을 살펴보지만 변경할 것이 없습니다. 이는 배열이 완전히 정렬되었음을 나타냅니다. 그리고 이것이 알고리즘 코드입니다. C로 구현해보세요! 버블 정렬 은 최악의 경우(모든 숫자가 틀림) O(n 2 ) 시간이 걸립니다. 각 반복마다 n 단계를 수행해야 하며 그 중 n개도 있기 때문입니다. 실제로 선택정렬 알고리즘의 경우와 마찬가지로 시간은 약간 줄어들지만(n 2 /2 – n/2), 이는 무시할 수 있다. 최선의 경우(모든 요소가 이미 제자리에 있는 경우) n 단계로 수행할 수 있습니다. Ω(n), 배열을 한 번만 반복하고 모든 요소가 제자리에 있는지 확인하면 되기 때문입니다(즉, n-1개 요소라도).
삽입 정렬
이 알고리즘의 주요 아이디어는 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누는 것입니다. 알고리즘의 각 단계에서 숫자는 정렬되지 않은 부분에서 정렬된 부분으로 이동합니다. 아래 예제를 사용하여 삽입 정렬이 어떻게 작동하는지 살펴보겠습니다. 시작하기 전에 모든 요소는 정렬되지 않은 것으로 간주됩니다. 1단계: 정렬되지 않은 첫 번째 값(3)을 가져와 정렬된 하위 배열에 삽입합니다. 이 단계에서 정렬된 전체 하위 배열의 시작과 끝은 바로 이 3개가 됩니다. 2단계: 3 > 5이므로 정렬된 하위 배열에 3의 오른쪽에 5를 삽입합니다. 3단계: 이제 정렬된 배열에 숫자 2를 삽입하는 작업을 수행합니다. 2를 오른쪽에서 왼쪽으로 값과 비교하여 올바른 위치를 찾습니다. 2 < 5 및 2 < 3이므로 정렬된 하위 배열의 시작 부분에 도달했습니다. 따라서 3의 왼쪽에 2를 삽입해야 합니다. 이렇게 하려면 2를 위한 공간이 있도록 3과 5를 오른쪽으로 이동하고 배열의 시작 부분에 삽입합니다. 4단계. 운이 좋네요: 6 > 5이므로 숫자 5 바로 뒤에 해당 숫자를 삽입할 수 있습니다. 5 단계. 4 < 6이고 4 < 5이지만 4 > 3입니다. 따라서 우리는 4를 삽입해야 한다는 것을 압니다. 3의 오른쪽. 다시, 4의 간격을 만들기 위해 5와 6을 오른쪽으로 이동해야 합니다. 완료되었습니다! 일반화 알고리즘: n의 정렬되지 않은 각 요소를 가져와 n에 적합한 위치를 찾을 때까지(즉, n보다 작은 첫 번째 숫자를 찾는 순간) 오른쪽에서 왼쪽으로 정렬된 하위 배열의 값과 비교합니다. . 그런 다음 이 숫자 오른쪽에 있는 모든 정렬된 요소를 오른쪽으로 이동하여 n을 위한 공간을 만들고 거기에 삽입하여 배열의 정렬된 부분을 확장합니다. 정렬되지 않은 각 요소 n에 대해 다음이 필요합니다.
n을 삽입해야 하는 배열의 정렬된 부분에서 위치를 결정합니다.
정렬된 요소를 오른쪽으로 이동하여 n에 대한 간격을 만듭니다.
배열의 정렬된 부분에서 결과 공백에 n을 삽입합니다.
그리고 여기에 코드가 있습니다! 자신만의 정렬 프로그램 버전을 작성하는 것이 좋습니다.
알고리즘의 점근적 속도
최악의 경우 두 번째 요소와 한 번 비교하고 세 번째 요소와 두 번 비교하는 식으로 진행됩니다. 따라서 우리의 속도는 O(n 2 )입니다. 기껏해야 이미 정렬된 배열을 사용하여 작업하는 것입니다. 요소를 삽입하거나 이동하지 않고 왼쪽에서 오른쪽으로 구성하는 정렬된 부분에는 Ω(n)의 시간이 걸립니다.
병합 정렬
이 알고리즘은 재귀적입니다. 하나의 큰 정렬 문제를 하위 작업으로 나누고 이를 실행하면 원래의 큰 문제 해결에 더 가까워집니다. 주요 아이디어는 정렬되지 않은 배열을 두 부분으로 나누고 개별 절반을 재귀적으로 정렬하는 것입니다. 정렬할 요소가 n개 있다고 가정해 보겠습니다. n < 2이면 정렬을 마치고, 그렇지 않으면 배열의 왼쪽과 오른쪽 부분을 별도로 정렬한 다음 결합합니다. 배열을 정렬해 보겠습니다. 배열을 두 부분으로 나누고, 분명히 정렬된 크기 1의 하위 배열을 얻을 때까지 계속 나눕니다. 두 개의 정렬된 하위 배열은 간단한 알고리즘을 사용하여 O(n) 시간에 병합할 수 있습니다. 각 하위 배열의 시작 부분에서 더 작은 숫자를 제거하고 병합된 배열에 삽입합니다. 모든 요소가 사라질 때까지 반복합니다. 병합 정렬은 모든 경우에 O(nlog n) 시간이 걸립니다. 각 재귀 수준에서 배열을 반으로 나누는 동안 log n을 얻습니다. 그런 다음 하위 배열을 병합하려면 n번만 비교하면 됩니다. 따라서 O(nlogn)입니다. 병합 정렬의 최상의 경우와 최악의 경우는 동일하며, 알고리즘의 예상 실행 시간 = Θ(nlog n)입니다. 이 알고리즘은 고려된 알고리즘 중에서 가장 효과적입니다.
그러나 어느 시점에서는 2차 함수가 1차 함수를 추월하게 되며 이를 피할 수 있는 방법이 없습니다. 또 다른 점근적 복잡성은 로그 시간 또는 O(log n)입니다. n이 증가함에 따라 이 함수는 매우 느리게 증가합니다. O(log n)은 정렬된 배열의 고전적인 이진 검색 알고리즘의 실행 시간입니다(강의에서 찢어진 전화번호부를 기억하시나요?). 배열을 2개로 나누고 요소가 위치한 절반을 선택하므로 검색 영역을 절반으로 줄일 때마다 요소를 검색합니다. 
처음으로 데이터 배열을 반으로 나누어 찾고 있는 것을 즉시 발견하면 어떻게 될까요? 가장 좋은 시간을 나타내는 용어가 있습니다 - Omega-large 또는 Ω(n). 이진 검색의 경우 = Ω(1)(배열 크기에 관계없이 일정한 시간에 찾습니다). 선형 검색은 검색되는 요소가 첫 번째 요소인 경우 O(n) 및 Ω(1) 시간에 실행됩니다. 또 다른 기호는 세타(Θ(n))입니다. 최선의 선택과 최악의 선택이 같은 경우에 사용됩니다. 이는 문자열의 길이를 별도의 변수에 저장한 예에 적합하므로 길이에 관계없이 이 변수를 참조하는 것으로 충분합니다. 이 알고리즘의 경우 최상의 경우와 최악의 경우는 각각 Ω(1) 및 O(1)입니다. 이는 알고리즘이 Θ(1) 시간에 실행된다는 것을 의미합니다.
선형 검색 함수는 두 개의 인수(키 키와 배열 array[])를 입력으로 받습니다. 키는 원하는 값(이전 예에서는 키 = 0)입니다. 배열은 우리가 원하는 숫자 목록입니다. 살펴보게 됩니다. 아무것도 찾지 못하면 함수는 -1(배열에 존재하지 않는 위치)을 반환합니다. 선형 검색으로 원하는 요소를 찾으면 함수는 배열에서 원하는 요소가 있는 위치를 반환합니다. 선형 검색의 좋은 점은 요소의 순서에 관계없이 모든 배열에 대해 작동한다는 것입니다. 우리는 여전히 전체 배열을 탐색할 것입니다. 이것이 그의 약점이기도 하다. 순서대로 정렬된 200개의 숫자 배열에서 숫자 198을 찾아야 하는 경우 for 루프는 198단계를 거치게 됩니다. 
정렬된 배열에 어떤 방법이 더 효과적인지 이미 짐작하셨을 것입니다.
선형적으로는 시간이 오래 걸릴 것입니다. 그리고 "디렉토리를 반으로 찢는 방법"을 사용하면 Jasmine으로 바로 이동하고 목록의 첫 번째 절반을 안전하게 삭제할 수 있으며 Mickey는 거기에 있을 수 없다는 것을 깨닫게 됩니다. 
동일한 원리를 사용하여 두 번째 열을 삭제합니다. 이 전략을 계속하면 몇 단계만 거치면 미키를 찾을 수 있습니다. 
숫자 144를 찾으세요. 목록을 반으로 나누고 숫자 13에 도달합니다. 우리가 찾고 있는 숫자가 13보다 큰지 작은지 평가합니다. 13 
< 144이므로 왼쪽에 있는 모든 것을 무시할 수 있습니다. 13 그리고 이 숫자 자체. 이제 검색 목록은 다음과 같습니다. 
요소 수가 짝수이므로 "중간"(시작 또는 끝에 더 가까움)을 선택하는 원칙을 선택합니다. 우리가 처음에 근접하는 전략을 선택했다고 가정해 보겠습니다. 이 경우 "중간" = 55. 
55 < 144입니다. 목록의 왼쪽 절반을 다시 버립니다. 운 좋게도 다음 평균 숫자는 144입니다. 
우리는 이진 검색을 사용하여 단 세 단계만으로 13개 요소 배열에서 144를 찾았습니다. 선형 검색은 동일한 상황을 최대 12단계로 처리합니다. 이 알고리즘은 각 단계에서 배열의 요소 수를 절반으로 줄이므로 점근 시간 O(log n)에서 필요한 요소를 찾습니다. 여기서 n은 목록의 요소 수입니다. 즉, 우리의 경우 점근 시간 = O(log 13)(3보다 조금 더 큼)입니다. 이진 검색 함수의 유사 코드: 
이 함수는 4개의 인수를 입력으로 사용합니다. 원하는 키, 원하는 키가 있는 데이터 배열 배열 [], min 및 max는 배열의 최대값과 최소값에 대한 포인터입니다. 우리는 알고리즘의 이 단계를 보고 있습니다. 우리의 예에서는 처음에 다음 그림이 제공되었습니다. 
코드를 더 분석해 보겠습니다. midpoint는 배열의 중간입니다. 이는 극단점에 따라 달라지며 그 사이의 중심에 위치합니다. 중간을 찾은 후에는 그것이 키 번호보다 작은지 확인합니다. 
그렇다면 키는 가운데 왼쪽에 있는 숫자보다 크며 이진 함수를 다시 호출할 수 있습니다. 이제 min = 중간점 + 1입니다. 키 < 중간점으로 판명되면 버릴 수 있습니다. 그 숫자 자체와 그의 오른쪽에 있는 모든 숫자. 그리고 최소 숫자부터 값(중간점 - 1)까지 배열을 통해 이진 검색을 호출합니다. 
마지막으로 세 번째 분기: 중간점의 값이 키보다 크지도 작지도 않으면 원하는 숫자가 될 수밖에 없습니다. 이 경우 이를 반환하고 프로그램을 종료합니다. 
마지막으로, 찾고 있는 숫자가 배열에 전혀 없는 경우가 발생할 수 있습니다. 이 사례를 고려하기 위해 다음 확인을 수행합니다. 
그리고 아무것도 찾지 못했음을 나타내기 위해 (-1)을 반환합니다. 여러분은 이진 검색을 위해서는 배열을 정렬해야 한다는 것을 이미 알고 있습니다. 따라서 특정 요소를 찾아야 하는 정렬되지 않은 배열이 있는 경우 두 가지 옵션이 있습니다.
주의: 실제 트리와는 달리 "프로그래머" 트리의 루트가 맨 위에 있습니다. 각 셀을 꼭짓점(Vertex)이라고 하며, 꼭짓점은 모서리(Edge)로 연결됩니다. 트리의 루트는 셀 번호 13입니다. 정점 3의 왼쪽 하위 트리는 아래 그림에서 색상으로 강조 표시됩니다. 
우리 트리는 이진 트리에 대한 모든 요구 사항을 충족합니다. 즉, 각 왼쪽 하위 트리에는 정점 값보다 작거나 같은 값만 포함되고, 오른쪽 하위 트리에는 정점 값보다 크거나 같은 값만 포함됩니다. 왼쪽 및 오른쪽 하위 트리는 모두 그 자체가 이진 하위 트리입니다. 이진 트리를 구성하는 방법은 유일한 방법이 아닙니다. 아래 그림에서 동일한 숫자 집합에 대한 다른 옵션을 볼 수 있으며 실제로는 많은 옵션이 있을 수 있습니다. 
이 구조는 검색을 수행하는 데 도움이 됩니다. 매번 위에서 왼쪽 및 아래로 이동하여 최소값을 찾습니다. 
최대 수를 찾으려면 위에서 아래로 오른쪽으로 이동합니다. 최소값이나 최대값이 아닌 숫자를 찾는 것도 매우 간단합니다. 우리는 정점이 우리가 찾고 있는 정점보다 크거나 작은지에 따라 루트에서 왼쪽이나 오른쪽으로 내려갑니다. 따라서 숫자 89를 찾아야 하는 경우 다음 경로를 따릅니다. 
숫자를 정렬 순서로 표시할 수도 있습니다. 예를 들어, 모든 숫자를 오름차순으로 표시해야 하는 경우 왼쪽 하위 트리를 선택하고 가장 왼쪽 꼭지점부터 위로 올라갑니다. 트리에 무언가를 추가하는 것도 쉽습니다. 기억해야 할 가장 중요한 것은 구조입니다. 트리에 값 7을 추가해야 한다고 가정하고 루트로 가서 확인해 보겠습니다. 숫자 7 < 13이므로 왼쪽으로 갑니다. 거기에서 5가 보이고 7 > 5이므로 오른쪽으로 이동합니다. 또한 7 > 8과 8에는 자손이 없으므로 왼쪽 8에서 가지를 만들고 여기에 7을 붙입니다. 또한 정점을 제거할 수도 있습니다 
. 그러나 이것은 다소 더 복잡합니다. 고려해야 할 세 가지 삭제 시나리오가 있습니다.
모든 숫자는 이전 숫자의 오른쪽 분기에 추가됩니다. 숫자를 찾고 싶다면 단순히 체인을 따라 내려가는 것 외에는 선택의 여지가 없습니다. 
선형 검색보다 낫지 않습니다. 더 복잡한 다른 데이터 구조도 있습니다. 하지만 지금은 고려하지 않겠습니다. 정렬된 목록에서 트리를 구성하는 문제를 해결하기 위해 입력 데이터를 무작위로 혼합할 수 있다고 가정해 보겠습니다.
주요 아이디어는 목록을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누는 것입니다. 알고리즘의 각 단계에서 새 숫자가 정렬되지 않은 부분에서 정렬된 부분으로 이동되는 방식으로 모든 숫자가 정렬된 부분에 포함될 때까지 계속됩니다.
배열의 정렬되지 않은 부분(즉, 이 단계에서는 전체 배열에서)에서 최소 숫자를 찾습니다. 이 숫자는 2입니다. 이제 정렬되지 않은 숫자 중 첫 번째 숫자로 변경하고 정렬된 배열의 끝에 넣습니다(이 단계에서는 첫 번째 위치). 이 단계에서는 이것이 배열의 첫 번째 숫자, 즉 3입니다. 
2단계. 우리는 숫자 2를 보지 않습니다; 그것은 이미 정렬된 하위 배열에 있습니다. 우리는 두 번째 요소부터 시작하여 최소값을 찾기 시작합니다. 이는 5입니다. 정렬되지 않은 요소 중 3이 최소값이고 정렬되지 않은 요소 중 첫 번째 요소가 5인지 확인합니다. 이들을 교환하고 정렬된 하위 배열에 3을 추가합니다. 
세 번째 단계에서는 정렬되지 않은 하위 배열에서 가장 작은 숫자가 4라는 것을 알 수 있습니다. 이를 정렬되지 않은 하위 배열 중 첫 번째 숫자인 5로 변경합니다. 
네 번째 단계에서는 정렬되지 않은 배열에서 가장 작은 숫자가 5라는 것을 알 수 있습니다. 6에서 변경하여 정렬된 하위 배열에 추가합니다. 
정렬되지 않은 숫자 중 하나의 숫자(가장 큰 숫자)만 남으면 전체 배열이 정렬되었음을 의미합니다! 
이것이 코드에서 배열 구현의 모습입니다. 직접 만들어 보세요. 
최선의 경우와 최악의 경우 모두 정렬되지 않은 최소 요소를 찾으려면 각 요소를 정렬되지 않은 배열의 각 요소와 비교해야 하며 각 반복마다 이를 수행합니다. 그러나 전체 목록을 볼 필요는 없고 정렬되지 않은 부분만 볼 필요가 있습니다. 이것이 알고리즘의 속도를 변경합니까? 첫 번째 단계에서는 5개 요소 배열에 대해 4번의 비교를 수행합니다. 두 번째에서는 3번, 세 번째에서는 2번입니다. 비교 횟수를 얻으려면 이 숫자를 모두 더해야 합니다. 우리는 합을 얻습니다 
. 따라서 최상의 경우와 최악의 경우에서 예상되는 알고리즘 속도는 Θ(n 2 )입니다. 가장 효율적인 알고리즘은 아닙니다! 그러나 교육 목적과 소규모 데이터 세트에는 상당히 적용 가능합니다.
1단계: 배열을 살펴봅니다. 알고리즘은 처음 두 요소인 8과 6으로 시작하여 순서가 올바른지 확인합니다. 8 > 6이므로 서로 바꿉니다. 다음으로 두 번째와 세 번째 요소를 살펴보겠습니다. 이제 이들은 8과 4입니다. 같은 이유로 이들을 교체합니다. 세 번째로 8과 2를 비교합니다. 전체적으로 (8, 6), (8, 4), (8, 2) 세 번의 교환을 수행합니다. 값 8은 목록의 올바른 위치에 "부동"되었습니다. 
2단계: (6,4)와 (6,2)를 교환합니다. 6은 이제 두 번째 위치에 있으므로 이미 정렬된 목록의 "꼬리"와 비교할 필요가 없습니다. 
3단계: 4와 2를 바꿉니다. 4개가 올바른 위치로 "떠오릅니다". 
4단계: 배열을 살펴보지만 변경할 것이 없습니다. 이는 배열이 완전히 정렬되었음을 나타냅니다. 
그리고 이것이 알고리즘 코드입니다. C로 구현해보세요! 버블 정렬 은 최악의 경우(모든 숫자가 틀림) 
O(n 2 ) 시간이 걸립니다. 각 반복마다 n 단계를 수행해야 하며 그 중 n개도 있기 때문입니다. 실제로 선택정렬 알고리즘의 경우와 마찬가지로 시간은 약간 줄어들지만(n 2 /2 – n/2), 이는 무시할 수 있다. 최선의 경우(모든 요소가 이미 제자리에 있는 경우) n 단계로 수행할 수 있습니다. Ω(n), 배열을 한 번만 반복하고 모든 요소가 제자리에 있는지 확인하면 되기 때문입니다(즉, n-1개 요소라도).
아래 예제를 사용하여 삽입 정렬이 어떻게 작동하는지 살펴보겠습니다. 시작하기 전에 모든 요소는 정렬되지 않은 것으로 간주됩니다. 
1단계: 정렬되지 않은 첫 번째 값(3)을 가져와 정렬된 하위 배열에 삽입합니다. 이 단계에서 정렬된 전체 하위 배열의 시작과 끝은 바로 이 3개가 됩니다. 
2단계: 3 > 5이므로 정렬된 하위 배열에 3의 오른쪽에 5를 삽입합니다. 
3단계: 이제 정렬된 배열에 숫자 2를 삽입하는 작업을 수행합니다. 2를 오른쪽에서 왼쪽으로 값과 비교하여 올바른 위치를 찾습니다. 2 < 5 및 2 < 3이므로 정렬된 하위 배열의 시작 부분에 도달했습니다. 따라서 3의 왼쪽에 2를 삽입해야 합니다. 이렇게 하려면 2를 위한 공간이 있도록 3과 5를 오른쪽으로 이동하고 배열의 시작 부분에 삽입합니다. 
4단계. 운이 좋네요: 6 > 5이므로 숫자 5 바로 뒤에 해당 숫자를 삽입할 수 있습니다. 5 
단계. 4 < 6이고 4 < 5이지만 4 > 3입니다. 따라서 우리는 4를 삽입해야 한다는 것을 압니다. 3의 오른쪽. 다시, 4의 간격을 만들기 위해 5와 6을 오른쪽으로 이동해야 합니다. 
완료되었습니다! 일반화 알고리즘: n의 정렬되지 않은 각 요소를 가져와 n에 적합한 위치를 찾을 때까지(즉, n보다 작은 첫 번째 숫자를 찾는 순간) 오른쪽에서 왼쪽으로 정렬된 하위 배열의 값과 비교합니다. . 그런 다음 이 숫자 오른쪽에 있는 모든 정렬된 요소를 오른쪽으로 이동하여 n을 위한 공간을 만들고 거기에 삽입하여 배열의 정렬된 부분을 확장합니다. 정렬되지 않은 각 요소 n에 대해 다음이 필요합니다.
정렬할 요소가 n개 있다고 가정해 보겠습니다. n < 2이면 정렬을 마치고, 그렇지 않으면 배열의 왼쪽과 오른쪽 부분을 별도로 정렬한 다음 결합합니다. 배열을 정렬해 보겠습니다. 
배열을 두 부분으로 나누고, 분명히 정렬된 크기 1의 하위 배열을 얻을 때까지 계속 나눕니다. 
두 개의 정렬된 하위 배열은 간단한 알고리즘을 사용하여 O(n) 시간에 병합할 수 있습니다. 각 하위 배열의 시작 부분에서 더 작은 숫자를 제거하고 병합된 배열에 삽입합니다. 모든 요소가 사라질 때까지 반복합니다. 
병합 정렬은 모든 경우에 O(nlog n) 시간이 걸립니다. 각 재귀 수준에서 배열을 반으로 나누는 동안 log n을 얻습니다. 그런 다음 하위 배열을 병합하려면 n번만 비교하면 됩니다. 따라서 O(nlogn)입니다. 병합 정렬의 최상의 경우와 최악의 경우는 동일하며, 알고리즘의 예상 실행 시간 = Θ(nlog n)입니다. 이 알고리즘은 고려된 알고리즘 중에서 가장 효과적입니다. 
GO TO FULL VERSION