관련 요약은 /p/60ea83ea17cc
를 참조하십시오임의 알고리즘의 최악의 작동 시간은 거의 항상 무작위화 알고리즘의 최악의 작동 시간과 같습니다. 중요한 차이점은 좋은 무작위 알고리즘에는 나쁜 입력이 없고, 나쁜 난수 (특정 입력에 상대적) 만 있다는 것이다.
예를 들어, 빠른 정렬의 경우 방법 A 는 첫 번째 요소를 피벗 요소로 사용하고 방법 B 는 임의로 선택된 요소를 피벗 요소로 사용합니다.
무작위 알고리즘을 통해 특정 입력은 더 이상 중요하지 않습니다. 중요한 것은 난수이다. 우리는 원하는 가동 시간을 얻을 수 있다. 이때 우리는 가능한 모든 난수에 대해 평균을 내고 모든 가능한 입력에 대해 평균을 구하는 것이 아니다.
난수에는 많은 알려진 통계적 특성이 있습니다. 의사 난수는 이러한 특성의 대부분을 충족시킵니다.
정말로 필요한 것은 난수의 시퀀스입니다. 이 숫자들은 독립적으로 나타나야 한다.
선형 합동 생성기
난수를 생성하는 가장 쉬운 방법은 1951 년 Lehmer 가 제안한 선형 동수 발생기입니다.
예: M = 11, x0 = 1
A = 7: 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, 7, 5, 2 ... (주기 10 = M-1)A = 5: 5, 3, 4, 9, 1, 5, 3, 4 ... (주기 5lt; M -1)
문제가 있는 난수 생성기 (반환 (0,1) 열린 간격 값): 곱셈 오버플로우
32 비트 시스템에서 작동하는 난수 생성기
증명: 왜 δ(xi) 가 0 또는 1
인가왜 나머지 값이 0 보다 작은 경우에만 δ(xi)=1
설명: 여기는 M 에 대한 잔여물이기 때문에 M 의 배수는 자연스럽게 제거된다. 그리고 δ(xi) 는 모두 정수 함수이므로 정수여야 하고, 다른 xi+1 은 항상 1~M-1 사이이므로 나머지가 0 보다 작으면 1
를 취합니다무작위화의 첫 번째 용도는 O(lgn) 예상 시간으로 조회 및 삽입된 데이터 구조를 지원하는 것입니다.
각 2 I 노드마다 다음 2 I 노드를 가리키는 포인터가 하나 있는데, 총 포인터 수는 두 배일 뿐이지만, 지금은 한 번의 조회에서 floor(lgn) 노드까지 최대 조사한다. 따라서 총 시간 소비는 O(lgn) 입니다.
본질적으로 이분법 찾기:
위의 데이터 구조의 구조 조건을 완화하면 점프 테이블이 구성됩니다:
만약 우리가 19 가 존재하는지 찾고 싶다면? 어떻게 찾나요? 우리는 처음부터 9 로 판단한다. 이때 9 보다 큰 다음 21 과 판단한다. 21 보다 작다. 이때 이 값은 반드시 9 점과 21 노드 사이에 있을 것이다. 이때 우리는 17 과 17 을 판단하고 17 보다 큰 다음 21 과 판단한다. 21 보다 작다면 17 노드와 21 노드 사이에 있을 것이다.
1) 구현
2) 공간 크기 소비
3) 찾기
1-2-3 점프 테이블의 구현 특징:
동일한 수준의 연결된 목록 (노드 3 개 이하) 에서 항목 보다 큰 첫 번째 노드를 찾은 다음 한 단계 아래로 이동합니다.
4) 삽입
높이가 H 인 새 노드를 추가할 때 높이가 H 인 4 개의 노드 사이에 간격이 생기지 않도록 해야 합니다.
2-3-4 트리를 사용하는 하향식 방법 삽입 (현재 노드가 4- 노드가 아닌지 확인): (참조 /p/8258ed821859 )
L 층에 있고 다음 층으로 내려가야 합니다. 다음 레이어의 간격 용량이 3 인 경우 간격의 중간 항목을 늘려 높이가 L 이 되도록 하여 용량이 1 인 두 개의 간격을 형성합니다. 이로 인해 아래로 삭제된 도로에서 용량 3 의 간격이 제거되므로 삽입은 안전합니다.
5) 삭제
2-3-4 나무를 사용하는 하향식 방법 제거 (현재 노드가 2- 노드가 아닌지 확인): (참조 /p/8258ed821859)
큰 수가 소수인지 여부를 결정하는 문제.
노드는 다음과 같습니다.
우선 순위가 가장 낮은 노드는 루트여야 합니다. 나무는 우선 순위에 따른 n! 항목의 n 이 아닌 가능한 배열을 심습니다! 에서 배열한 것입니다.
1) 삽입
삽입 후, 왼손잡이와 오른손으로 힙 순서 특성 복원:
2) 삭제
이 삭제 방법은 또한 빨간색 블랙 트리의 삭제 방법을 사용하여 삭제를 리프 노드의 삭제로 귀결할 수 있습니다. (후계자를 사용하면 많은 회전을 절약할 수 있음)