(۰۱ خرداد ۱۳۹۳ ۰۹:۴۵ ب.ظ)be_sooye_movafaghiat نوشته شده توسط:  سلام...

سوالم این هست که آیا برای جست و جو در لیست پیوندی نامرتب می تونیم از جست و جوی دودویی استفاده کنیم و از مرتبه logn این کار رو انجام بدیم یا اینکه خیر؟

کلا بهترین، بدترین و حالت میانگین الگوریتم جست و جو در لیست پیوندی نامرتب و مرتب از چه مرتبه زمانی هست؟

(در مورد درج و حذف از لیست پیوندی هم اگر همین سوال رو پاسخ بدید ممنون میشم.)

مرسی ازتون...

سلام

الگوریتم جستجو در لیست پیوندی (یک طرفه ساده) نامرتب همانند جستجوی خطیه چون مقایسه عمل اصلی محسوب میشه پس در بهترین حالت آن مرتبه زمانی از (۱) o است یعنی در ابتدای لیست(عنصر اول) باشد.
بدترین حالت اینکه شما تمامی عناصر موجود در لیست پیوندی رو مقایسه کنید تا از مرتبه (n) یعنی عنصر در انتهای لیست باشد و در حالت متوسط هم به این صورت است که
عنصر اول با یک مقایسه
عنصر دوم با دو مقایسه
عنصر سوم با سه مقایسه
و
..
عنصر N ام با n مقایسه
حال مجموع
۱+۲+۳+ ...+n که برابر با n(n+1)/2 است . حالا برای بدست آوردن حالت متوسط حاصل راتقسیم به تعداد کل آن یعنی n می شود که نهایتا از مرتبه (n) اوی خواهد بود.
موفق باشید

(۰۲ خرداد ۱۳۹۳ ۰۳:۱۹ ب.ظ)m!r@ نوشته شده توسط:  

(01 خرداد ۱۳۹۳ ۰۹:۴۵ ب.ظ)be_sooye_movafaghiat نوشته شده توسط:  سلام...

سوالم این هست که آیا برای جست و جو در لیست پیوندی نامرتب می تونیم از جست و جوی دودویی استفاده کنیم و از مرتبه logn این کار رو انجام بدیم یا اینکه خیر؟

کلا بهترین، بدترین و حالت میانگین الگوریتم جست و جو در لیست پیوندی نامرتب و مرتب از چه مرتبه زمانی هست؟

(در مورد درج و حذف از لیست پیوندی هم اگر همین سوال رو پاسخ بدید ممنون میشم.)

مرسی ازتون...

سلام

الگوریتم جستجو در لیست پیوندی (یک طرفه ساده) نامرتب همانند جستجوی خطیه چون مقایسه عمل اصلی محسوب میشه پس در بهترین حالت آن مرتبه زمانی از (۱) o است یعنی در ابتدای لیست(عنصر اول) باشد.
بدترین حالت اینکه شما تمامی عناصر موجود در لیست پیوندی رو مقایسه کنید تا از مرتبه (n) یعنی عنصر در انتهای لیست باشد و در حالت متوسط هم به این صورت است که
عنصر اول با یک مقایسه
عنصر دوم با دو مقایسه
عنصر سوم با سه مقایسه
و
..
عنصر N ام با n مقایسه
حال مجموع
۱+۲+۳+ ...+n که برابر با n(n+1)/2 است . حالا برای بدست آوردن حالت متوسط حاصل راتقسیم به تعداد کل آن یعنی n می شود که نهایتا از مرتبه (n) اوی خواهد بود.
موفق باشید

خیلی ممنونم ازتون دوست عزیز...

در مورد لیست مرتب چه طور؟
و همین طور مرتبه درج و حذف

خیلی خیلی خیلی ممنون