کمینه و بیشینه با هم
عضوها را جفت‌جفت برمی‌دارد: کوچک‌ترِ جفت فقط با کمینه و بزرگ‌ترش فقط با بیشینه مقایسه می‌شود؛ ۳ مقایسه برای هر ۲ عضو.
پیدا کردن کمینه به تنهایی n − 1 مقایسه لازم دارد و بیشینه هم همین‌قدر؛ اگر جدا پیدا شوند 2n − 2 مقایسه. ترفند این الگوریتم: عضوها را جفت‌جفت بردار. اول دو عضو جفت را با هم مقایسه کن؛ کوچک‌تر فقط کاندیدای کمینه است و بزرگ‌تر فقط کاندیدای بیشینه. پس برای هر دو عضو فقط ۳ مقایسه لازم است.
- زمان:
about 3n/2 comparisons - حافظه:
O(1) - CLRS، بخش ۹.۱
- جانسون‌باو، فصل ۴
هشت عدد: ۱ مقایسه برای جفت اول و ۳ مقایسه برای هر یک از سه جفت بعدی، روی هم ۱۰ مقایسه به‌جای ۱۴.
def min_max(a):n = len(a)if n % 2 == 1:lo = a[0]hi = a[0]start = 1else:if a[0] < a[1]:lo = a[0]hi = a[1]else:lo = a[1]hi = a[0]start = 2for i in range(start, n - 1, 2):if a[i] < a[i + 1]:small = a[i]big = a[i + 1]else:small = a[i + 1]big = a[i]if small < lo:lo = smallif big > hi:hi = bigreturn lo, hi
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
Call stack
- min_max()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- ورودی فعلی (n=8)
نمایش به شکل جدول
| n | comparisons |
|---|---|
| 4 | 4 |
| 6 | 7 |
| 8 | 10 |
| 10 | 13 |
| 12 | 16 |
| 14 | 19 |
| 16 | 22 |
توضیح
ایده
پیدا کردن کمینه به تنهایی n − 1 مقایسه لازم دارد و بیشینه هم همین‌قدر؛ اگر جدا پیدا شوند 2n − 2 مقایسه. ترفند این الگوریتم: عضوها را جفت‌جفت بردار. اول دو عضو جفت را با هم مقایسه کن؛ کوچک‌تر فقط کاندیدای کمینه است و بزرگ‌تر فقط کاندیدای بیشینه. پس برای هر دو عضو فقط ۳ مقایسه لازم است.
هزینه
حداکثر 3⌊n/2⌋ مقایسه، یعنی حدود 1.5n به‌جای 2n. این بهترین ممکن هم هست: هیچ الگوریتمی با مقایسه نمی‌تواند با کمتر از ⌈3n/2⌉ − 2 مقایسه هر دو را پیدا کند.
در trace به چه چیزی نگاه کنی
- فلش
iاولین عضو هر جفت را نشان می‌دهد؛loوhiدر پنل حافظه‌اند. - شمار
compareرا با2n − 2مقایسه کن.