جست‌وجوی پرشی
Jump Searchجست‌وجوی پرشی یک الگوریتم از دسته جست‌وجو است. این الگوریتم فضای جست‌وجو را پیمایش یا محدود می‌کند تا target پیدا شود یا نبودنش ثابت شود.
اول این مفهوم را در ذهن نگه دار
جست‌وجوی پرشی یک الگوریتم از دسته جست‌وجو است. این الگوریتم فضای جست‌وجو را پیمایش یا محدود می‌کند تا target پیدا شود یا نبودنش ثابت شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم جست‌وجوی پرشی ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع O(√n) است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
اول پیش‌شرط‌ها را بنویس: مرتب بودن؟ توزیع؟ random access؟
بازه یا state جست‌وجو را شفاف نگه دار.
مطمئن شو هر مرحله واقعاً به termination نزدیک می‌شود.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای جست‌وجوی پرشی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
O(√n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- الگوریتم را با structure و وضعیت preprocessing داده هماهنگ انتخاب کن.
کجا معمولاً اشتباه می‌کنیم؟
- نقض پیش‌شرط الگوریتم.
- خطای مرزی و شرط پایان.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای جست‌وجوی پرشی در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی O(√n) و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
جست‌وجوی پرشی چه مسئله‌ای را حل می‌کند؟
جست‌وجوی پرشی یک الگوریتم از دسته جست‌وجو است. این الگوریتم فضای جست‌وجو را پیمایش یا محدود می‌کند تا target پیدا شود یا نبودنش ثابت شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(√n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نقض پیش‌شرط الگوریتم.