جست‌وجوی خطی
Linear SearchLinear Search عناصر را یکی‌یکی بررسی می‌کند تا target پیدا شود یا به انتهای مجموعه برسیم.
اول این مفهوم را در ذهن نگه دار
Linear Search عناصر را یکی‌یکی بررسی می‌کند تا target پیدا شود یا به انتهای مجموعه برسیم.
چطور کار می‌کند؟ ساده و مرحله‌ای
به مرتب بودن داده یا preprocessing نیاز ندارد.
در بدترین حالت همه n عنصر بررسی می‌شوند، پس زمان O(n) است.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
اول پیش‌شرط‌ها را بنویس: مرتب بودن؟ توزیع؟ random access؟
بازه یا state جست‌وجو را شفاف نگه دار.
مطمئن شو هر مرحله واقعاً به termination نزدیک می‌شود.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای جست‌وجوی خطی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function linearSearch(items, target) {
for (let i = 0; i < items.length; i++) {
if (items[i] === target) return i;
}
return -1;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- الگوریتم را با structure و وضعیت preprocessing داده هماهنگ انتخاب کن.
کجا معمولاً اشتباه می‌کنیم؟
- نقض پیش‌شرط الگوریتم.
- خطای مرزی و شرط پایان.
مدل یک پاسخ حرفه‌ای
در مصاحبه آن را صرفاً الگوریتم بد معرفی نکن؛ برای داده کوچک، نامرتب یا جست‌وجوی یک‌باره می‌تواند ساده‌ترین انتخاب درست باشد.
جست‌وجوی خطی چه مسئله‌ای را حل می‌کند؟
Linear Search عناصر را یکی‌یکی بررسی می‌کند تا target پیدا شود یا به انتهای مجموعه برسیم.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نقض پیش‌شرط الگوریتم.