Randomized Algorithms (expected time, seeds) — சீரற்ற வழிமுறைகள்

சீரற்ற — எதிர்பார்ப்பு வேகம்; QuickSort pivot; சோதனையில் seed நிலை.

உண்மை உலகில் இது ஏன் முக்கியம்?

சுமை சமநிலை — சீரற்ற shard. தொழில்நுட்பம் — மாதிரி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

random vs secrets; எதிர்பார்ப்பு பகுப்பாய்வு.

Pythonில் முயற்சி செய்வோம்

import random


def random_pivot_partition(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    p = random.choice(a)
    low = [x for x in a if x < p]
    eq = [x for x in a if x == p]
    high = [x for x in a if x > p]
    return random_pivot_partition(low) + eq + random_pivot_partition(high)


random.seed(0)
print(random_pivot_partition([3, 1, 4, 1, 5])[:5])

அடிக்கடி நேரும் தவறுகள்

• mod bias.
• CI flaky.

முக்கியச் சுருக்கக் குறிப்புகள்

• Las Vegas / Monte Carlo.
• எதிரி உள்ளீடு — random pivot.