拉斯維加斯算法

在電腦運算中，拉斯維加斯算法（Las Vegas algorithm）是一種永遠給出正確解的隨機化算法；也就是說，它總是給出正確結果，或是返回失敗。 換言之，拉斯維加斯算法不賭結果的正確性，而是賭運算所用資源。一個簡單的例子是隨機快速排序，他的中心點雖然是隨機選擇的，但排序結果永遠一致。

與拉斯維加斯算法相對的是蒙地卡羅算法。蒙地卡羅算法在一定的概率下可能返回錯誤的結果，但其運行時間是確定的或有上界的。

特性

• 隨機性：算法在運行過程中使用隨機數來影響其行為。
• 正確性保證：拉斯維加斯算法總是返回正確的結果。也就是說，它不會在計算結果上出錯。
• 運行時間不確定：雖然結果總是正確的，但算法的運行時間是隨機的，可能會有很大的波動。

使用拉斯維加斯算法的快速排序代碼示例

一個經典的拉斯維加斯算法例子是快速排序的隨機化版本。在這個版本中，算法隨機選擇一個樞軸（pivot）元素進行分區。雖然運行時間的期望值是 $O(n\log n)$，但實際運行時間會因為隨機選擇而有所不同。然而，無論運行時間如何，最終排序結果總是正確的。

偽代碼示例

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())

解釋

1. randomizedQuickSort：這是主函數，用於對數組 A 的子數組 [low, high] 進行排序。
2. randomizedPartition：這是隨機化的分區函數，它隨機選擇一個樞軸，並將其與當前子數組的最後一個元素交換，然後調用 partition 函數進行分區。
3. partition：這是標準的分區函數，使用最後一個元素作為樞軸，將小於等於樞軸的元素移動到樞軸的左邊，大於樞軸的元素移動到右邊，最後返回樞軸的位置。
4. swap：這是一個簡單的交換函數，用於交換數組中的兩個元素。
5. random：這是一個生成 [low, high] 範圍內隨機整數的函數。

C++ 示例

#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;
}