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;
}
这是一篇小作品。您可以通过编辑或修订扩充其内容。 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.