سلام، امروز من قصد دارم سریالی با عنوان “الگوریتمی که هر برنامه نویس باید بداند” را شروع کنم. در این مجموعه قصد داریم الگوریتم های مختلفی مانند جستجو ، مرتب سازی ، نمودارها ، آرایه ها و … را بررسی کنیم.
امروز اولین قسمت را با الگوریتم جستجو شروع می کنیم. ما قصد داریم 4 الگوریتم جستجو را بررسی کنیم که هر برنامه نویس باید آنها را بداند.
جستجوی خطی
در علوم کامپیوتر ، جستجوی خطی یا جستجوی پی در پی روشی برای یافتن عنصری در لیست است. این مورد به طور متوالی هر عنصر از لیست را بررسی می کند تا زمانی که یک تطابق پیدا شود یا کل لیست جستجو شود.
در جستجوی خطی ، ما عنصر هدف را در لیست به ترتیب متوالی یکی یکی از اولین عنصر لیست تا آخرین جستجو می کنیم.
بهترین حالت: مقدار هدف در جایگاه اول لیست قرار دارد
بدترین حالت: مقدار هدف در آخرین موقعیت لیست است
چه موقع باید استفاده کرد:
- وقتی لیست مرتب نشده است
- وقتی لیست کوچک است
جستجوی دودویی
در علوم کامپیوتر ، جستجوی باینری ، همچنین به عنوان جستجوی نیم فاصله ، جستجوی لگاریتمی یا دودویی شناخته می شود ، یک الگوریتم جستجو است که موقعیت یک مقدار هدف را در یک آرایه مرتب شده پیدا می کند. جستجوی دودویی مقدار هدف را با عنصر میانی آرایه مقایسه می کند. اگر برابر نباشند ، نیمی که هدف نمی تواند در آن قرار بگیرد حذف می شود و جستجو در نیمه باقیمانده ادامه می یابد ، دوباره عنصر میانی را می گیرد تا با مقدار مورد نظر مقایسه شود.
در جستجوی دودویی ، لیست باید به ترتیب مرتب شده باشد. ما با انتخاب مقدار از وسط لیست و مقایسه آن ، مقدار مورد نظر را جستجو کردیم. اگر مطابقت نداشته باشد ، اگر مقدار هدف کمتر از عنصر میانی باشد ، نیمه اولیه افت می کند در غیر این صورت نیمه خاتمه افت می کند. این روند تا زمانی که مقدار مورد نظر را پیدا نکنیم ادامه خواهد یافت.
بهترین حالت: مقدار هدف در موقعیت میانی لیست است
بدترین حالت: مقدار هدف در اولین یا آخرین موقعیت لیست است
چه موقع باید استفاده کرد:
- وقتی لیست مرتب باشد
- وقتی لیست بزرگ است
جستجو عمق اول (DFS)
Depth-first search (DFS) الگوریتمی برای پیمایش یا جستجوی ساختارهای داده درخت یا نمودار است. الگوریتم از گره ریشه شروع می شود (انتخاب برخی از گره های دلخواه به عنوان گره ریشه در مورد نمودار) و تا آنجا که ممکن است در امتداد هر شاخه قبل از برگشت پیمایش کنید.
در DFS ، ما ریشه نمودار ، درخت یا ساختار داده را انتخاب می کنیم و هر شاخه را به ترتیب کاوش می کنیم. وقتی شاخه ای انتخاب می شود ، قبل از تغییر به شاخه ای دیگر ، همه زیرشاخه های آن را کاوش می کند.
بهترین حالت: مقدار هدف در موقعیت ریشه درخت است
بدترین حالت: مقدار هدف در نوک زیر شاخه آخرین شاخه مرتب شده است
چه موقع باید استفاده کرد:
- هنگامی که درخت بسیار گسترده است
- وقتی مقدار هدف در اعماق درخت واقع شود
جستجو اول سطح (BFS)
جستجوی اولین سطح (BF-1) الگوریتمی برای پیمایش یا جستجوی ساختارهای داده های درخت یا نمودار است. این کار از ریشه درخت شروع می شود (یا برخی از گره های دلخواه یک نمودار ، که گاهی اوقات به عنوان “کلید جستجو” نیز شناخته می شود) ، و قبل از انتقال به گره ها در سطح عمق بعدی ، همه گره های همسایه را در عمق فعلی کاوش می کند.
در BSF ، همانند DFS ، ما گره ریشه نمودار ، درخت یا ساختار داده را انتخاب می کنیم. بعد از گره ، به تمام گره های مجاور آن و سپس به سطح بعدی که همه گره مجاور شاخه است ، حرکت می کنیم.
بهترین حالت: مقدار هدف در موقعیت ریشه درخت است
بدترین حالت: مقدار هدف در نوک طولانی ترین شاخه درخت است
چه موقع باید استفاده کرد:
- هنگامی که مقدار هدف دور از ریشه درخت نباشد
- هنگامی که درخت بسیار عمیق است ، و مقدار هدف نادر است.