کل فصل در یک جمله: مسئله را به چند نمونه‌ی کوچک‌تر بشکن، هر کدام را جدا حل کن، بعد جواب‌ها را بچسبان. پنج مثال این فصل فقط پنج شکل مختلفِ همین جمله‌اند.
نام این روش از یک تکنیک جنگی گرفته شده: در سال ۱۸۰۵ ارتش روسی و اتریشی با بیش از ۱۵ هزار نفر به جنگ ناپلئون آمدند. ناپلئون با تقسیم نیروهای دشمن به دو بخش، بر آن‌ها پیروز شد؛ در واقع با تقسیم سپاه بزرگ به دو سپاه کوچک‌تر و پیروز شدن بر تک‌تک آن‌ها، موفق شد آن سپاه بزرگ را شکست دهد.
در تکنیک تقسیم و غلبه، یک مسئله به چند نمونه‌ی کوچک‌تر تقسیم می‌شود، سپس این نمونه‌های کوچک‌تر حل شده و با ترکیب جواب آن‌ها، جواب مسئله‌ی اصلی حاصل می‌شود. اگر این نمونه‌های کوچک‌تر قابل حل نبودند، آن‌قدر آن‌ها را به نمونه‌های کوچک‌تر تقسیم می‌کنیم تا بالاخره حل شوند. این روش در واقع یک روش حل از بالا به پایین (Top-down) است.
جستجوی دودویی فقط در آرایه‌های مرتب کار می‌کند. ایده: عنصر مورد نظر را با خانه‌ی وسط مقایسه کن.
| خانه | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| مقدار | 12 | 20 | 25 | 27 | 29 | 30 | 33 | 44 | 45 | 67 | 78 | 80 |
| گام | محدوده | mid | مقایسه | تصمیم |
|---|---|---|---|---|
| ۱ | Low=1 , High=12 | (1+12)/2 = 6 | x[6]=30 | ۳۰ < ۴۴ ⟹ نیمه‌ی بالایی، Low = 7 |
| ۲ | Low=7 , High=12 | (7+12)/2 = 9 | x[9]=45 | ۴۵ > ۴۴ ⟹ نیمه‌ی پایینی، High = 8 |
| ۳ | Low=7 , High=8 | (7+8)/2 = 7 | x[7]=33 | ۳۳ < ۴۴ ⟹ Low = 8 |
| ۴ | Low=8 , High=8 | 8 | x[8]=44 | برابر شد ⟹ پیدا شد |
int bsearch(int x[ ], int n, int m) { int low, high, mid; low=0; high=n-1; while(low<=high) { mid=(low + high)/2; if(m<x[mid]) high=mid-1; else if(m>x[mid]) low=mid+1; else return mid; } return -1; }
int bsearch(int low, int high, int m, int x[ ]) { int mid; if (low > high) return -1; else { mid=(low + high)/2; if(m==x[mid]) return mid; else if(m<x[mid]) return bsearch(low, mid-1, m, x); else return bsearch(mid+1, high, m, x); } }
در بدترین حالت، عدد مورد جستجو (بزرگ‌ترین عنصر آرایه) در نهایت در خانه‌ای است که تنها یک عمل مقایسه لازم دارد:
با باز کردن ساده (بدون هیچ تغییر متغیری — چون اندازه هر بار نصف می‌شود، نه جذر):
توقف وقتی n/2k = 1 یعنی k = log₂ n، و چون W(1) = 1:
و با قضیه‌ی کمکی T(n) = aT(n/b) + c:
اینجا a=1, b=2, c=1 ⟹ W(n) = Θ(log n).
در مثال قبلی با ۱۲ خانه، حداکثر ⌊log₂ 12⌋ + 1 = 4 مقایسه داشتیم ✔ — پس ⌊log₂ n⌋ + 1 برابر ارتفاع درخت دودویی متعادل است.
فرض کنید آرایه‌ی ۵ خانه‌ای 11 22 33 44 55 مرتب است. درخت جستجوی دودویی (BST) آن:
در درخت BST، مقدار هر گره = تعداد مقایسه‌ها برای یافتن آن عنصر (ریشه ۱ مقایسه، فرزندان ۲ مقایسه، ...).
روش دقیق‌تر: تعداد گره‌های هر سطح را در شماره‌ی سطح ضرب کن و جمع بزن، بعد بر تعداد گره‌ها تقسیم کن:
(این نمونه برای آرایه‌ی ۹ عنصری است که درختش سطح ۴ هم دارد.)
برای جستجوی ناموفق، گره‌های فرضی (مربعی) را به شکل درخت رسم می‌کنیم و همان روش را تکرار می‌کنیم:
برای مثال ۵ عنصری قبلی هم: U(n) = (2+2+3+3+3+3)/6 = 16/6.
تست با اعداد مثال: S = (1 + 1/5)(16/6) − 1 = 16/5 − 1 = 11/5 ✔
⌊log₂ n⌋ + 1 است؛ پس جستجوی دودویی در حالت ناموفق هم‌مرتبه با Θ(log₂ n) است. برای یافتن عنصر در حالت موفق: بهترین حالت ۱ مقایسه، بدترین ⌊log₂ n⌋ + 1، و میانگین از مرتبه‌ی Θ(log₂ n).
قبل از توضیح مرتب‌سازی ادغامی، باید بدانیم ادغام دو لیست مرتب در یک لیست مرتب جدید چگونه است.
ادغام (Merge): دو دسته‌ی مرتب داریم. در هر مرحله کارت جلویی هر دسته را با کارت جلویی دسته‌ی مقابل مقایسه می‌کنیم و کارت با شماره‌ی کوچک‌تر را در دسته‌ی جدید قرار می‌دهیم. هرگاه یکی از دسته‌ها خالی شد، تمام کارت‌های باقی‌مانده در دسته‌ی دیگر را در انتهای دسته‌ی جدید قرار می‌دهیم.
void merge(int p, int m, int A[ ], int B[ ], int S[ ]) { int i,j,k; i=j=k=0; while(i<p && j<m) { if(A[i]<B[j]) { S[k]=A[i]; i++; } else { S[k]=B[j]; j++; } k++; } if(i==p) while(j<m) // تمام مابقی عناصر B را در انتهای S قرار بده { S[k]=B[j]; k++; j++; } else if(j==m) while(i<p) // تمام مابقی عناصر A را در انتهای S قرار بده { S[k]=A[i]; k++; i++; } }
وقتی همه‌ی عناصر یک آرایه از اولین عنصر آرایه‌ی دیگر کوچک‌تر باشند؛ مثلاً A = 3 5 6 8 و B = 12 18 25 29 36 ⟹ فقط ۴ مقایسه.
وقتی همه‌ی عناصر آرایه‌ی اول (به جز آخرین عضو) از اولین عنصر آرایه‌ی دوم کوچک‌تر باشند و آن آخرین عضو از تمام عناصر آرایه‌ی دوم بزرگ‌تر باشد ⟹ ۸ مقایسه.
اگر مجموع عناصر A و B را p + m = n بگیریم، آنگاه:
n/2 عنصر، تقسیم کن.void mergesort(int n, int S[ ]) { if(n>1) { Copy S[0] through S[{n/2}-1] to A[0] through A[{n/2}-1]; Copy S[n/2] through S[n-1] to B[0] through B[{n/2}-1]; mergesort(n/2, A); mergesort(n/2, B); merge(n/2, n/2, A, B, S); } }
تابع mergesort به صورت بازگشتی ۲ بار خودش را صدا می‌زند و پس از آن تابع ادغام merge فراخوانی می‌شود.
با قضیه‌ی اصلی: a=2, b=2, k=1 ⟹ nlog₂2 = n1 = n ⟹ حالت تساوی:
در حالت‌های خوب و متوسط هم مرتبه‌ی Θ(n log n) است — یعنی در هر حال مرتب‌سازی ادغامی همیشه n log n است.
در الگوریتم مرتب‌سازی ادغامی، در هر مرحله نیاز به حافظه‌ی کمکی به اندازه‌ی n خانه داریم؛ مثلاً در مرحله‌ی اول که آرایه‌ی S به دو آرایه‌ی A و B تقسیم می‌شود، جمع خانه‌های A و B برابر n است.
با بهینه‌سازی می‌توان merge و mergesort را طوری نوشت که مرتبه‌ی فضای مصرفی Θ(n) باشد (به جای Θ(n log n)).
قبل از توضیح این مرتب‌سازی، لازم است الگوریتم مهم پارتیشن (Partition) را بیان کنیم.
در الگوریتم پارتیشن، یک عنصر محوری یا لولا (Pivot) انتخاب شده و سایر عناصر بندابه‌به گونه‌ای جابه‌جا می‌شوند که کلیه‌ی عناصر بزرگ‌تر از آن در یک طرف و کلیه‌ی عناصر کوچک‌تر از آن در طرف دیگر عنصر لولا قرار گیرند. عنصر لولا اغلب اولین عنصر سمت چپ آرایه فرض می‌شود. در واقع با الگوریتم پارتیشن، جای درست قرارگیری عنصر pivot در آرایه‌ی مرتب‌شده‌ی نهایی را به دست می‌آوریم.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| x | 26 | 5 | 37 | 1 | 61 | 11 | 59 | 15 | 48 | 19 |
در ابتدا i به اولین خانه و j به آخرین خانه اشاره می‌کند و pivot برابر x[0] یعنی ۲۶ است.
i از سمت چپ مرتباً زیاد می‌شود تا به اولین عنصر بزرگ‌تر از ۲۶ برسد ⟹ ۳۷j از سمت راست مرتباً کم می‌شود تا به اولین عنصر کوچک‌تر از ۲۶ برسد ⟹ ۱۹دوباره حلقه تکرار می‌شود: i به ۶۱ و j به ۱۵ می‌رسند ⟹ جابه‌جا می‌شوند:
عملیات تا آنجا تکرار می‌شود که i و j از یکدیگر عبور کنند (i >= j). در مرحله‌ی بعد j به ۱۱ و i به ۵۹ اشاره می‌کنند ⟹ i>=j ⟹ تمام. در نهایت ۲۶ با x[j] یعنی ۱۱ جابه‌جا می‌شود:
int partition(int x[ ], int left, int right) { int t; int i=left; int j=right+1; int pivot=x[left]; do { do i++; while(x[i]<pivot); do j--; while(x[j]>pivot); if(i<j) { t=x[i]; x[i]=x[j]; x[j]=t; } } while(i<j); t=x[left]; x[left]=x[j]; x[j]=t; return j; }
left اندیس خانه سمت چپ آرایه و right اندیس خانه راست آرایه است.
اگر عمل اصلی در تابع فوق را مقایسه‌ی خانه‌های آرایه‌ی x با pivot در نظر بگیریم، این تعداد مقایسه همواره برابر n−1 است؛ چرا که تمام عناصر به جز عنصر محور با pivot مقایسه می‌شوند:
partition به گونه‌ای جابه‌جا می‌شوند که کلیه‌ی عناصر بزرگ‌تر از آن در یک سمت و کلیه‌ی عناصر کوچک‌تر از آن در طرف دیگر لولا قرار گیرند.void quicksort(int x[ ], int left, int right) { int pivotpoint; if(left<right) { pivotpoint=partition(x, left, right); quicksort(x, left, pivotpoint-1); // مرتب‌سازی زیر لیست چپ quicksort(x, pivotpoint+1, right); // مرتب‌سازی زیر لیست راست } }
| # | وضعیت آرایه | توضیح |
|---|---|---|
| ۰ | [26 5 37 1 61 11 59 15 48 19] | pivot = 26 |
| ۱ | [11 5 19 1 15] 26 [59 61 48 37] | ۲۶ در جای نهایی |
| ۲ | [1 5] 11 [19 15] 26 [59 61 48 37] | pivot = 11 |
| ۳ | [1] 5 11 [19 15] 26 [59 61 48 37] | pivot = 5 |
| ۴ | 1 5 11 [15 19] 26 [59 61 48 37] | pivot = 19 |
| ۵ | 1 5 11 15 19 26 [48 37] [59 61] | pivot = 59 |
| ۶ | 1 5 11 15 19 26 37 [48] [59 61] | pivot = 48 |
| ۷ | 1 5 11 15 19 26 37 48 59 61 | مرتب شد |
انتخاب عنصر لولا تأثیر مهمی در سرعت اجرا دارد. اگر این عنصر، عنصر میانه‌ی آرایه باشد، آرایه را به دو زیرآرایه تقریباً مساوی تقسیم خواهیم نمود و می‌توان ثابت نمود در این شرایط بهترین حالت روی داده است.
اما اگر عنصر لولا کوچک‌ترین یا بزرگ‌ترین عنصر آرایه باشد، در این شرایط یکی از زیرآرایه‌ها تهی خواهد شد و می‌توان اثبات کرد در این شرایط بدترین حالت روی داده است.
عمل عنصر لولا به صورت تصادفی انتخاب می‌شود. یک روش مناسب دیگر برای انتخاب لولا روش میانه‌ی سه (Median of three) است که در آن میانه‌ی مقادیر کلیدهای اول، وسط و آخر به عنوان عنصر لولا می‌شود. مثلاً برای کلیدهای 26, 61, 19 داریم: Median(26, 61, 19) = 26.
اگر عنصر لولا، عنصر اول به عنوان محور انتخاب شود، بدترین حالت زمانی رخ می‌دهد که آرایه از قبل مرتب باشد (یا به صورت نزولی مرتب شده باشد). چرا؟ چون تابع partition در هر بار مقدار left را به عنوان pivotpoint برمی‌گرداند و لذا آرایه به صورت یک زیرآرایه خالی در سمت چپ و یک زیرآرایه با n−1 عنصر در سمت راست تقسیم می‌شود:
در حالت متوسط، آرایه تقریباً نصف می‌شود و به همان رابطه‌ی T(n) = 2T(n/2) + Θ(n) می‌رسیم.
Θ(n) خواهد بود و در حالت متوسط نیاز به فضای پشته Θ(log n) است.O(n²) می‌شود.| الگوریتم | بهترین حالت | حالت متوسط | بدترین حالت |
|---|---|---|---|
| مرتب‌سازی سریع | O(n log n) | O(n log n) | O(n²) |
| مرتب‌سازی ادغام | O(n log n) | O(n log n) | O(n log n) |
الگوریتم ساده‌ی ضرب ماتریس‌های n×n:
for(i=1; i<=n; i++) for(j=1; j<=n; j++) { C[i][j]=0; for(k=1; k<=n; k++) C[i][j]=C[i][j]+A[i][k]*B[k][j]; }
در این برنامه فوق دو ماتریس A و B ضرب شده و حاصل را در ماتریس C می‌ریزد. سه ماتریس n×n هستند.
با تغییر ساده زیر می‌توان تعداد جمع‌ها را کاهش داد:
for(i=1; i<=n; i++) for(j=1; j<=n; j++) { C[i][j]=A[i][1]*B[1][j]; for(k=2; k<=n; k++) C[i][j]=C[i][j]+A[i][k]*B[k][j]; }
در هر حال مشاهده می‌شود که مرتبه‌ی ضرب‌ها و جمع‌ها تغییر نکرده و همان Θ(n³) باقی مانده است.
می‌توانیم جمع‌های تکراری را حذف کنیم. مثلاً:
⟹ تبدیل به ⟹
اگر n توانی از ۲ باشد، می‌توان ماتریس‌های A و B را به چهار ماتریس کوچک‌تر n/2 × n/2 تقسیم نمود:
اگر در الگوریتم بالا عمل ضرب را در نظر بگیریم، آنگاه تعداد ضرب‌ها برای ماتریس‌های n×n به ۸ عمل ضرب ماتریس‌های n/2 × n/2 نیاز خواهد داشت. از طرف دیگر، ضرب دو ماتریس ۱×۱ فقط به یک عمل ضرب اسکالر نیاز دارد؛ لذا:
اشتراسن ثابت کرد که می‌توان با تغییر فرمول‌ها تعداد ضرب‌ها را کاهش داد. مثلاً برای محاسبه‌ی A = x·y و B = x·y·z می‌توان نوشت B = A·z (از دو ضرب به یک ضرب). با همین ترفند، حاصل ضرب دو ماتریس A×B یعنی ماتریس C از روابط زیر به دست می‌آید:
با این تکنیک یک عمل ضرب کم شده ولی در عوض ۱۴ عمل جمع و تفریق اضافه شده است. بنابراین در مقادیر بزرگ n، در کل زمان مصرفی کاهش می‌یابد، چرا که ضرب به مراتب زمان بیشتری نسبت به جمع و تفریق می‌برد.
بدیهی است که برای حالت n = 1، یعنی ضرب ماتریس‌های ۱×۱، تنها به یک عمل ضرب و صفر عمل جمع و تفریق نیاز داریم.
Θ(n²) نیاز دارد، ولی هنوز کسی نتوانسته است الگوریتمی از مرتبه ۲ برای ضرب ماتریس‌ها ابداع کند و از طرف دیگر نیز کسی نتوانسته اثبات کند نوشتن چنین الگوریتمی غیرممکن است.همان‌طور که می‌دانید اعداد صحیح بزرگ را می‌توان توسط آرایه ذخیره کرد. مثلاً عدد بزرگ 8,173,963,563 را به صورت زیر ذخیره می‌کنیم:
اسکن فصل دقیقاً تا همین‌جا ادامه دارد و بقیه‌ی این مثال در صفحه‌ی بعدِ کتاب است که در فایل شما نیست.
x = a·10n/2 + b و y = c·10n/2 + d. ضرب ساده ۴ ضرب کوچک‌تر می‌خواهد (ac, ad, bc, bd)، ولی با ترفند کاراتسوبا (Karatsuba) می‌شود با ۳ ضرب انجامش داد:
xy = ac·10n + ((a+b)(c+d) − ac − bd)·10n/2 + bd ⟹ T(n) = 3T(n/2) + Θ(n) = Θ(nlog₂3) ≈ Θ(n1.58).
| مسئله | رابطه‌ی بازگشتی | مرتبه | نکته |
|---|---|---|---|
| جستجوی دودویی | W(n)=W(n/2)+1 | Θ(log n) | a=1 در قضیه‌ی کمکی |
| ادغام دو لیست | W(n)=n−1 | Θ(n) | بهترین: Min(p,m) |
| مرتب‌سازی ادغامی | W(n)=2W(n/2)+n−1 | Θ(n log n) | همیشه n log n |
| پارتیشن | T(n)=n−1 | Θ(n) | یک عنصر در جای نهایی |
| مرتب‌سازی سریع (بدترین) | W(n)=W(n−1)+(n−1) | Θ(n²) | آرایه‌ی از قبل مرتب |
| مرتب‌سازی سریع (بهترین/میانگین) | T(n)=2T(n/2)+Θ(n) | Θ(n log n) | لولا میانه |
| ضرب ماتریس استاندارد | T(n)=8T(n/2) | Θ(n³) | ۸ ضرب |
| ضرب ماتریس اشتراسن | T(n)=7T(n/2) | Θ(n2.81) | ۷ ضرب، ۱۸ جمع |
کتاب در پایان هر مثال، سؤالاتی به عنوان تمرین مطرح کرده است. این‌ها را خودت حل کن؛ راهنما بازشو است، جواب نیست.
S(n) = (1+1/n)U(n) − 1 با روش استقرا. ۳) برای آرایه‌ی ۱۰۰ عنصری، بدترین حالت چند مقایسه است؟n−1 است و تعداد سطح‌ها log n. ۳) چرا مرتب‌سازی ادغامی برای داده‌های روی هارد مناسب است؟[26 5 37 1 61 11 59 15 48 19] خودت قدم‌به‌قدم اجرا کن و هر جابه‌جایی را بنویس. ۲) اگر آرایه از قبل صعودی مرتب باشد، چرا pivot اول بدترین حالت است؟ ۳) روی همان آرایه، لولا را با روش میانه‌ی سه انتخاب کن و تعداد سطح‌های بازگشت را با حالت قبل مقایسه کن.M7 را حساب کن. ۲) بررسی کن چرا log₂7 = 2.81. ۳) اگر n توانی از ۲ نباشد چه می‌کنیم و این کار چه هزینه‌ای دارد؟T(n) = aT(n/b) + f(n). سه عدد را پیدا کن: a، b، و مرتبه‌ی f(n).logb a را حساب کن و با توان k در f(n) مقایسه کن.√n یا n−1)، از تغییر متغیر یا باز کردن استفاده کن.