Parsa Mehdipour
Parsa Mehdipour
خواندن ۳ دقیقه·۲ سال پیش

ساختار داده : قسمت سوم

در این قسمت میخوام عملیات جستجو کردن که بر روی ساختار های داده (فعلا آرایه) انجام میشه رو بررسی کنم پس با من همراه باشید.




جستجو کردن(Search) :

عملیات جستجو بر روی آرایه ها به این معناست که بگردیم و ببینیم که آیا یک مقدار(value) مشخص در آرایه موجود هست یا نه. و اگر موجود بود در چه موقعیتی(index) قرار دارد.

یک جورایی معکوس عملیات خواندن(Read) میشه. چون عملیات خواندن به این معناست که ما یک موقعیت(index) رو به کامپیوتر معرفی میکنیم و مقدار(value) موجود در اون موقعیت(index) رو میخونیم. ولی در عملیات جستجو(Search) ما یک مقدار(value) رو به کامپیوتر معرفی میکنیم و موقعیت(index) ای که آن مقدار(value) در آن قرار دارد رو ازش میخوایم.

این دو عملیات (خواندن و جستجو کردن) ممکن هست شبیه به هم به نظر برسند ولی دنیایی تفاوت از نظر کارایی(efficiency) بینیشون قرار داره.خواندن(Read) از یک موقعیت(index) مشخص سریع هست، به دلیل اینکه کامپیوتر به راحتی میتونه وارد یک موقعیت(index) بشه و مقدارش(value) رو بخونه. ولی جستجو کردن(Search) کسل کننده هست، چون که کامپیوتر این قابلیت رو نداره که بتونه مستقیما وارد یک مقدار(value) بشه.

این یک نکته مهمی هست : کامپیوتر دسترسی مستقیم به تمامی memory address های خودش داره. ولی هیچ اطلاعی از مقادیری که در آنها ذخیره شده نداره.

مثال خودمون رو در نظر بگیریم که در قسمت های قبل داشتیم که آرایه ای از میوه ها بود. به عنوان مثال کامپیوتر نمیتونه در اصل مقادیر موجود در هر سلول رو ببینه. برای کامپیوتر آرایه ما چیزی شبیه به شکل زیر هست.

برای جستجو کردن یک میوه در آرایه ما، کامپیوتر راهی نداره جز اینکه دونه به دونه سلول هارو بررسی بکنه.

حالا باهم تمام مراحلی که کامپیوتر برای جستجو کردن(Search) مقدار "dates" انجام میده رو بررسی میکنیم. برای یادآوری آرایه موردنظرمون رو دوباره براتون میارم.

  • اول از همه کامپیوتر موقعیت(index) 0 رو چک میکنه:
  • به دلیل اینکه مقدار موجود در موقعیت 0 برابر با "apples" هست و با مقدار ای که ما مد نظرمون داریم برابر نیست، کامپیوتر وارد موقعیت بعدی میشه:
  • موقعیت 1 مقدار "dates" رو درخودش نداره پس وارد موقعیت 2 میشیم:
  • و دوباره هم مقدار مورد نظرمون در این موقعیت قرار ندارد پس وارد موقعیت بعدی میشیم:
  • بالاخره پیدا شد!! ، در نتیجه کامپیوتر مقدار "dates" رو پیدا کرد و میدونه که در موقعیت 3 قرار داره. از اینجا به بعد کامپیوتر دیگه نیاز نداره که وارد موقعیت بعدی بشه چون مقدار مورد نظرمون پیدا شده.
در این مثال چون کامپیوتر برای پیدا کردن "dates" مجبور بود که 4 تا سلول(cell) رو بررسی بکنه تا این مقدار پیدا بشه، میتونیم بیان کنیم که این عملیات مشخص در مجموع 4 قدم(step) برداشته.
این مدل از جستجو کردن که در آن کامپیوتر مجبور به چک کردن دونه به دونه سلول(cell) ها هست، معروف به جستجوی linear هست(linear search).

و حالا یک سوال : بیشترین تعداد قدمی(step) که یک کامپیوتر برای انجام linear search نیاز داره برداره چندتا هست ؟

اگر مقداری(value) که ما دنبالش هستیم در آخرین سلول(cell) قرار داشته باشه (به عنوان مثال "elderberries")، در نهایت کامپیوتر مجبور به بررسی کردن تمام سلول های آرایه هست تا زمانی که این مقدار رو پیدا کنه. همچنین اگر این مقدار اصلا در آرایه ما قرار نداشته باشه باز هم کامپیوتر مجبور به بررسی کردن تمام سلول ها میشه تا مطمئن بشه که این مقدار در آرایه وجود نداره.

پس نتیجه میگیریم که برای یک آرایه ای با 5 عضو بیشترین تعداد قدم(step) هایی که برای یک linear search برداشته میشه برابر هست با 5، و برای یک آرایه ای با 500 عضو برابر هست با 500.

راه دیگه برای بیان این جمله به صورت زیر هست:

برای آرایه ای با N عضو بیشترین قدم(step) هایی که یک linear search برمیداره برابر هست با N.

به همین دلیل هست که جستجو کردن(Search) کارآمدی(efficiency) کمتری نسبت به خواندن(Read) داره، چون یک جستجو ممکن هست که تعداد قدم(step) های زیادی برداره ولی خواندن همیشه در یک قدم(step) انجام میشه و اندازه آرایه اصلا در آن مهم نیست.

ساختار دادهالگوریتمارایهlinear searcharray
Back-End Developer
شاید از این پست‌ها خوشتان بیاید