Loading AI tools
永远给出正确解的随机化算法 来自维基百科,自由的百科全书
在電腦運算中,拉斯維加斯算法是一種永遠給出正確解的隨機化算法;也就是說,它總是給出正確結果,或是返回失敗。 換言之,拉斯維加斯算法不賭結果的正確性,而是賭運算所用資源。一個簡單的例子是隨機快速排序,他的中心點雖然是隨機選擇的,但排序結果永遠一致。
![]() |
與拉斯維加斯算法相對的是蒙地卡羅算法。蒙地卡羅算法在一定的概率下可能返回錯誤的結果,但其運行時間是確定的或有上界的。
一個經典的拉斯維加斯算法例子是快速排序的隨機化版本。在這個版本中,算法隨機選擇一個樞軸(pivot)元素進行分區。雖然運行時間的期望值是 ,但實際運行時間會因為隨機選擇而有所不同。然而,無論運行時間如何,最終排序結果總是正確的。
function randomizedQuickSort(A, low, high)
if low < high then
pivotIndex = randomizedPartition(A, low, high)
randomizedQuickSort(A, low, pivotIndex - 1)
randomizedQuickSort(A, pivotIndex + 1, high)
function randomizedPartition(A, low, high)
pivotIndex = random(low, high) // 在 [low, high] 范围内随机选择一个枢轴
swap(A[pivotIndex], A[high]) // 将随机选择的枢轴与最后一个元素交换
return partition(A, low, high)
function partition(A, low, high)
pivot = A[high]
i = low - 1
for j = low to high - 1 do
if A[j] <= pivot then
i = i + 1
swap(A[i], A[j])
swap(A[i + 1], A[high])
return i + 1
function swap(a, b)
temp = a
a = b
b = temp
function random(low, high)
// 返回 [low, high] 范围内的一个随机整数
return low + floor((high - low + 1) * rand())
A
的子數組 [low, high]
進行排序。partition
函數進行分區。[low, high]
範圍內隨機整數的函數。#include <iostream>
#include <cstdlib>
#include <ctime>
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(array[i], array[j]);
}
}
swap(array[i + 1], array[high]);
return i + 1;
}
int randomizedPartition(int array[], int low, int high) {
int pivotIndex = low + rand() % (high - low + 1); // 在 [low, high] 范围内随机选择一个枢轴
swap(array[pivotIndex], array[high]); // 将随机选择的枢轴与最后一个元素交换
return partition(array, low, high);
}
void randomizedQuickSort(int array[], int low, int high) {
if (low < high) {
int pivotIndex = randomizedPartition(array, low, high);
randomizedQuickSort(array, low, pivotIndex - 1);
randomizedQuickSort(array, pivotIndex + 1, high);
}
}
int main() {
srand(time(0)); // 设置随机数种子
int array[] = {3, 6, 8, 10, 1, 2, 1};
int n = sizeof(array) / sizeof(array[0]);
std::cout << "Original array: ";
for (int i = 0; i < n; i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
randomizedQuickSort(array, 0, n - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
return 0;
}
![]() | 這是一篇小作品。您可以透過編輯或修訂擴充其內容。 |