Las Vegas Algorithm
লাস ভেগাস অ্যালগরিদম
Randomness ব্যবহার করেও সবসময় সঠিক উত্তর দেয় এমন randomized algorithm — ফলাফল নির্ভুল, শুধু running time random হয়।
also: las vegas
Deterministic algorithm কোনো না কোনো input-এ দুর্বল — random choice সেই adversarial input-কেই অস্ত্রহীন করে।
guarantee: উত্তর 100% সঠিক
variable : কত সময় (expected time-এ bound দেওয়া যায়)ক্লাসিক উদাহরণ: randomized quicksort — pivot random হলে যেকোনো input-এ expected O(n log n); কেউ consistently খারাপ input বানাতে পারে না। Shuffle করে quicksort চালানোও একই কৌশল।
Monte Carlo-র সাথে সম্পর্ক উল্টো: Monte Carlo fixed সময়ে ভুল হতে পারে; Las Vegas-এ time budget বসালে সেটা Monte Carlo-র মতো আচরণ করে।