در این مقاله ، ما تجزیه و تحلیل ریاضی از پیچیدگی زمان و فضا جستجوی باینری را برای موارد مختلف مانند بدترین حالت ، مورد متوسط و بهترین مورد ارائه داده ایم. ما تعداد دقیق مقایسه ها را در جستجوی باینری ارائه داده ایم.
توجه: ما از پیچیدگی زمان و فضا در نماد Big-O استفاده کرده ایم.
جدول محتویات :
- مبانی جستجوی باینری
- تجزیه و تحلیل بهترین پیچیدگی زمان جستجوی باینری
- تجزیه و تحلیل میانگین پیچیدگی زمان مورد در جستجوی باینری
- تجزیه و تحلیل پیچیدگی زمان بدترین مورد جستجوی باینری
- تجزیه و تحلیل پیچیدگی فضایی جستجوی باینری
- نتیجه
- بهترین پیچیدگی زمان جستجوی باینری: O (1)
- میانگین پیچیدگی زمان مورد جستجوی باینری: O (logn)
- بدترین حالت پیچیدگی جستجوی باینری: O (logn)
- پیچیدگی فضایی جستجوی باینری: O (1) برای تکراری ، O (ورود به سیستم) برای بازگشتی.
مبانی جستجوی باینری
برای درک کامل جستجوی باینری از این مقاله ها عبور کنید:
جستجوی باینری یک الگوریتم به طور کارآمد یک عنصر را در یک لیست معین از عناصر مرتب شده جستجو می کند. جستجوی باینری اندازه مجموعه داده ها را در هر مرحله به نصف جستجو می کند.
اجرای تکراری جستجوی Bianry به شرح زیر است:
بگذارید با تجزیه و تحلیل ریاضی جستجوی باینری شروع کنیم.
بهترین پیچیدگی زمان جستجوی باینری
بهترین مورد جستجوی باینری زمانی اتفاق می افتد:
- عنصر جستجو در وسط لیست است
در این حالت ، این عنصر در اولین قدم خود یافت می شود و این شامل 1 مقایسه است.
بنابراین ، بهترین پیچیدگی زمان جستجوی باینری o (1) است.
میانگین پیچیدگی زمان مورد در جستجوی باینری
بگذارید تعداد مشخصی وجود داشته باشد: A1 ، A2 ،. A (n-1) ،
ما باید عنصر P. را پیدا کنیم
دو مورد وجود دارد:
مورد 1: عنصر P می تواند در شاخص های متمایز از 0 تا N-1 باشد. مورد 2: یک مورد وجود خواهد داشت که عنصر P در لیست موجود نباشد. مورد 1 و 1 مورد 2 وجود دارد. بنابراین ، موارد مشخصی وجود دارد که باید در کل در نظر گرفته شود.
اگر عنصر P در شاخص K باشد ، جستجوی باینری مقایسه K+1 را انجام می دهد.
این بخاطر این است که:
عنصر در شاخص N/2 را می توان در 1 مقایسه با شروع جستجوی باینری از وسط یافت.
به طور مشابه ، در مقایسه 2 ، عناصر در شاخص N/4 و 3N/4 بر اساس نتیجه مقایسه 1 مقایسه می شوند.
در این خط ، در مقایسه 3 ، عناصر در فهرست N/8 ، 3N/8 ، 5N/8 ، 7N/8 بر اساس نتیجه مقایسه 2 مقایسه می شوند.
بر این اساس ، ما می دانیم که:
- عناصر نیاز به 1 مقایسه: 1
- عناصر نیاز به 2 مقایسه: 2
- عناصری که نیاز به 3 مقایسه دارند: 4
بنابراین، عناصری که نیاز به مقایسه I دارند: 2^(I-1)
حداکثر تعداد مقایسه = تعداد دفعات N بر 2 تقسیم می شود به طوری که نتیجه 1 = مقایسه برای رسیدن به عنصر اول = مقایسه logN
من می توانم از 0 تا logN تغییر کنم
تعداد کل مقایسه = 1 * (عناصر نیاز به 1 مقایسه) + 2 * (عناصر نیاز به 2 مقایسه) + .+ logN * (عناصری که نیاز به مقایسه logN دارند)
تعداد کل مقایسه ها = 1 * (1) + 2 * (2) + 3 * (4) + .+ logN * (2^(logN-1))
تعداد کل مقایسه ها = 1 + 4 + 12 + 32 + .= 2^logN * (logN - 1) + 1
تعداد کل مقایسه ها = N * (logN - 1) + 1
تعداد کل موارد = N+1
بنابراین، میانگین تعداد مقایسه = ( N * (logN - 1) + 1 ) / (N+1)
میانگین تعداد مقایسه = N * logN / (N+1) - N/(N+1) + 1/(N+1)
عبارت غالب N * logN / (N+1) است که تقریباً logN است. بنابراین، میانگین پیچیدگی زمانی موردی جستجوی باینری O(logN) است.
تجزیه و تحلیل پیچیدگی زمان بدترین مورد جستجوی باینری
بدترین حالت جستجوی باینری زمانی اتفاق می افتد که:
- عنصر این است که جستجو در اولین فهرست یا آخرین فهرست است
در این مورد، تعداد کل مقایسه های مورد نیاز، مقایسه های logN است.
بنابراین، بدترین حالت پیچیدگی زمانی جستجوی باینری O(logN) است.
تجزیه و تحلیل پیچیدگی فضایی جستجوی باینری
در اجرای تکراری جستجوی باینری، پیچیدگی فضا O(1) خواهد بود.
این به این دلیل است که برای پیگیری دامنه عناصری که باید بررسی شوند به دو متغیر نیاز داریم. هیچ داده دیگری مورد نیاز نیست.
در اجرای بازگشتی جستجوی باینری، پیچیدگی فضا O(logN) خواهد بود.
این به این دلیل است که در بدترین حالت، تماس های بازگشتی logN وجود خواهد داشت و همه این تماس های بازگشتی در حافظه انباشته می شوند. در واقع، اگر مقایسه I مورد نیاز باشد، آنگاه فراخوانی های بازگشتی I در حافظه انباشته می شوند و از تجزیه و تحلیل ما از میانگین پیچیدگی زمانی مورد، می دانیم که میانگین حافظه O(logN) نیز خواهد بود.
نتیجه
نتیجه تجزیه و تحلیل پیچیدگی زمان و مکان جستجوی باینری به شرح زیر است:
- بهترین پیچیدگی زمان جستجوی باینری: O (1)
- میانگین پیچیدگی زمان مورد جستجوی باینری: O (logn)
- بدترین حالت پیچیدگی جستجوی باینری: O (logn)
- پیچیدگی فضایی جستجوی باینری: O (1) برای تکراری ، O (ورود به سیستم) برای بازگشتی.
با استفاده از این مقاله در OpenGenus، باید ایده کامل تجزیه و تحلیل الگوریتم جستجوی باینری را داشته باشید. لذت بردن.
Ue Kiao، دکترا
UE Kiao یک نویسنده فنی و توسعه دهنده نرم افزار با B. SC در علوم کامپیوتر در دانشگاه ملی تایوان و دکترای الگوریتم ها در انستیتوی فناوری توکیو |محقق Taobao
بهبود یافته و بررسی شده توسط:
aditya chatterjee
بنیاد OpenGenus
پیچیدگی زمانی
پیچیدگی زمانی برای مرتب سازی مبتنی بر غیر سازگار
ما توضیح داده ایم که چرا حداقل پیچیدگی زمانی نظری مشکل مرتب سازی مبتنی بر غیر مقایسه ای O (n) به جای O (n logn) است. این باید مطالعه شود. این بینش های جدید را باز خواهد کرد.
دکتری ue kiao
پیچیدگی زمان و فضا جستجوی خطی [تجزیه و تحلیل ریاضی]
ما تجزیه و تحلیل ریاضی از پیچیدگی زمان و فضا جستجوی خطی برای موارد مختلف مانند بدترین حالت ، میانگین مورد و بهترین حالت را ارائه داده ایم. ما تعداد دقیق مقایسه ها را در جستجوی خطی ارائه داده ایم.
دکتری ue kiao
