Algorythm Design (4)

‫روش تقسیم و حل‬ ‫‪Divide & Conquer‬‬ ‫‪Technique‬‬ ‫طراحی الگوریتم ها ‪ -‬دانشگاه فردوسی مشهد ‪ -‬صمد‬ ‫پایدار‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬

‫مقدمه‬ ‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪2‬‬

‫مقدمه‬ ‫‪‬‬

‫برخی مسائل دارای خاصیت تقسیم پذیری می باشند‪.‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫یعنی برای حل مساله برای اندازه ورودی ‪ ،n‬می توان ابتدا مساله را‬ ‫به تعدادی زیرمساله با اندازه ورودی کوچکتر از ‪ n‬تقسیم کرده و آن‬ ‫زیرمسائل را حل کرده و با استفاده از جوابهای آن زیرمسائل‪،‬‬ ‫جواب مساله اصلی را بدست آورد‪.‬‬

‫مثل برای پیدا کردن بزرگترین عنصر یک لیست می توانیم آن‬ ‫لیست را به دو قسمت تقسیم کرده و بزرگترین عنصر هر‬ ‫قسمت را تعیین کرده و سپس در بین دو مقدار حاصل‪،‬‬ ‫بزرگترین مقدار را بعنوان بزرگترین عنصر لیست در نظر‬ ‫بگیریم‪.‬‬ ‫روش تقسیم و حل‪ ،‬روش رایجی برای حل چنین مسائلی‬ ‫می باشد‪.‬‬

‫‪3‬‬

‫مقدمه‬ ‫‪‬‬

‫گامهای روش تقسیم و حل برای حل یک‬ ‫مساله‬ ‫‪‬‬

‫‪‬‬

‫مرحله ‪ :1‬تقسیم مساله به تعدادی زیرمساله‬ ‫کوچکتر )که انتظار داریم حل آنها نسبت به حل‬ ‫مساله اصلی ساده تر باشد( )مرحله ‪(divide‬‬ ‫مرحله ‪ :2‬هر یک از زیر مسائل حاصل را به روش‬ ‫تقسیم و حل‪ ،‬حل می کنیم )به شیوه بازگشتی(‪.‬‬ ‫‪‬‬

‫‪‬‬

‫عمل تقسیم مساله به زیر مسائل کوچکتر را تا جایی‬ ‫ادامه می دهیم که زیر مسائل حاصل به سادگی قابل حل‬ ‫باشند )مرحله ‪.(conquer‬‬

‫مرحله ‪ :3‬با ادغام و ترکیب کردن نتایج زیرمسائل‪،‬‬ ‫جواب مساله اصلی را بدست می آوریم‪.‬‬ ‫‪4‬‬

‫مقدمه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫یک روش بال به پایین )‪ (top-down‬است‪.‬‬ ‫ذاتا یک روش بازگشتی است‪.‬‬ ‫در برخی مسائل‪ ،‬نیازی نیست تمام زیرمسائل را‬ ‫حل کنیم‪.‬‬ ‫در برخی مسائل نیازی به ادغام نتایج زیرمسائل‬ ‫نمی باشد‪.‬‬ ‫وقتی یک مساله را به تعدادی زیرمساله تقسیم‬ ‫می کنیم‪ ،‬معمول هرچه اندازه زیرمسائل بهم‬ ‫نزدیکتر باشد‪ ،‬کارآیی الگوریتم بهتر است‪.‬‬

‫‪5‬‬

‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪6‬‬

‫جستجوی دودویی‬ ‫‪‬‬

‫صورت مساله‪ :‬آرایه ای شامل ‪ n‬عدد صحیح‬ ‫داریم که به طور غیر نزولی مرتب شده‬ ‫است‪ .‬مطلوب است الگوریتمی که عدد ‪ x‬را‬ ‫در این آرایه جستجو کرده و در صورتی که‬ ‫عدد در آرایه وجود داشت‪ ،‬اندیس وقوع آن را‬ ‫برگرداند و در غیر اینصورت عدد ‪ -1‬را‬ ‫برگرداند‪.‬‬

‫‪7‬‬

‫جستجوی دودویی‬ ‫‪‬‬

‫راه حل‪ :‬عنصر وسط آرایه را بررسی می کنیم اگر با ‪ x‬برابر‬ ‫بود اندیس آن را بر می گردانیم و کار تمام است‪ .‬در غیر‬ ‫اینصورت‪ ،‬اگر ‪ x‬در آرایه باشد‪ ،‬با توجه به مرتب بودن آرایه‪،‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬

‫اگر مقدار ‪ x‬از مقدار عنصر وسط کوچکتر باشد‪ ،‬آنگاه ‪ x‬در مجموعه‬ ‫سمت چپ عنصر وسط )قبل از آن( می باشد‪ .‬بنابراین به جستجوی ‪x‬‬ ‫در نیمه سمت چپ آرایه می پردازیم‪.‬‬ ‫اگر مقدار ‪ x‬از مقدار عنصر وسط بزرگتر باشد‪ ،‬آنگاه ‪ x‬در مجموعه‬ ‫سمت راست عنصر وسط )بعد از آن( می باشد‪ .‬بنابراین به جستجوی ‪x‬‬ ‫در نیمه سمت راست آرایه می پردازیم‪.‬‬ ‫بدین ترتیب بطور ضمنی‪ ،‬مساله را به دو زیرمساله کوچکتر تقسیم‬ ‫کرده ایم که البته تنها یکی از این زیرمسائل را حل خواهیم نمود‪.‬‬

‫هر بار طول آرایه مورد جستجو‪ ،‬تقریبا نصف می شود‪.‬‬

‫‪8‬‬

‫جستجوی دودویی‬ int binSearch(int low , int high, int x) { if (low > high) return -1; // not found mid = (low + high) / 2; if ( x == A[mid] ) return mid; // conquer else if ( x > A[mid] ) return binSearch(mid+1, high, x); //divide else if ( x < A[mid] ) return binSearch(low, mid-1, x); //divide } 9

‫جستجوی دودویی‬ ‫‪‬‬

‫‪‬‬

‫برای جستجوی عنصر ‪ x‬در آرایه ‪ A‬با ‪ n‬عنصر‪،‬‬ ‫تابع قبل را بصورت ‪(binSearch(0, n-1, x‬‬ ‫فراخوانی می کنیم‪.‬‬ ‫در این مثال‪ ،‬هر مساله به دو زیرمساله‬ ‫تقسیم می شود که فقط یکی از آنها حل می‬ ‫شود و نیازی به مرحله ادغام و ترکیب نتایج‬ ‫نیز نمی باشد‪.‬‬

‫‪10‬‬

‫جستجوی دودویی‬ ‫‪‬‬ ‫‪‬‬

‫تحلیل الگوریتم و محاسبه مرتبه زمانی آن‬ ‫واضح است که حجم کار انجام شده توسط‬ ‫الگوریتم‪ ،‬علوه بر اندازه آرایه‪ ،‬به مقدار‬ ‫عناصر آن و همچنین مقدار ‪ x‬نیز بستگی دارد‬ ‫‪ ‬بجای محاسبه ‪ (T(n‬به محاسبه ‪ (B(n‬و‬ ‫‪ (W(n‬و ‪ (A(n‬می پردازیم‪.‬‬

‫‪11‬‬

‫جستجوی دودویی‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫محاسبه ‪ :(B(n‬تابع پیچیدگی زمانی بهترین حالت‬ ‫ورودی‪ :‬آرایه ‪ A‬و مقدار ‪x‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر آرایه ‪ A‬که آن را با ‪n‬‬ ‫نمایش می دهیم‪.‬‬ ‫عمل کلیدی‪ :‬عمل مقایسه )‪([x==A[mid‬‬ ‫محاسبه ‪ :(B(n‬حالتی که عنصر ‪ x‬در اولین‬ ‫فراخوانی پیدا شود )یعنی ‪ x‬برابر عنصر وسط‬ ‫آرایه باشد(‬ ‫)‪B(n) = 1;  B(n)=O(1‬‬

‫‪12‬‬

‫جستجوی دودویی‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫محاسبه ‪ :(W(n‬تابع پیچیدگی زمانی بدترین حالت‬ ‫ورودی‪ :‬آرایه ‪ A‬و مقدار ‪x‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر آرایه ‪ A‬که آن را با ‪n‬‬ ‫نمایش می دهیم‪.‬‬ ‫عمل کلیدی‪ :‬عمل مقایسه )‪([x==A[mid‬‬ ‫محاسبه ‪ W(n): x‬در آخرین فراخوانی تابع پیدا‬ ‫شود یا اصل ‪ x‬در آرایه نباشد‪.‬‬ ‫‪W(n) = W(n/2) + 1‬‬ ‫= ‪= W(n/4) + 1 + 1 = W(n/8) + 1 + 1 +1‬‬ ‫…‬ ‫‪= W(n/2k) + k‬‬ ‫‪13‬‬

‫جستجوی دودویی‬ ‫‪W(n) = W(n/2k) + k W(n) = logn2 ‬‬ ‫‪W(1) = 1‬‬ ‫)‪W(n) = O(logn‬‬ ‫‪n/2k = 1  k = logn2‬‬ ‫‪‬‬

‫مرتبه زمانی الگوریتم در بدترین حالت‪،‬‬ ‫لگاریتمی می باشد‪.‬‬

‫‪14‬‬

‫جستجوی دودویی‬ ‫‪‬‬

‫محاسبه مرتبه زمانی حالت متوسط ‪(A(n :‬‬

‫‪15‬‬

‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪16‬‬

‫مرتب سازی با ادغام‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫کامل مبتنی بر الگوی تقسیم و حل‬ ‫ابتدا آرایه را به دو قسمت تقسیم کن )‪(trivial‬‬ ‫نیمه اول آرایه را جداگانه مرتب کن و نیمه دوم‬ ‫آرایه را هم جداگانه مرتب کن‬ ‫دو نیمه مرتب شده را طوری با هم ادغام کن‬ ‫که حاصل نیز مرتب باشد‪.‬‬ ‫برای مرتب کردن هر یک از نیم آرایه ها‪ ،‬از‬ ‫همین روش استفاده کن و عمل نصف کردن‬ ‫آرایه را تا جایی ادامه بده که تنها یک عنصر‬ ‫داشته باشد‪.‬‬ ‫‪17‬‬

‫مرتب سازی با ادغام‬ ‫‪‬‬

‫مثال‬ ‫‪10, 5, 4, 12, 8, 6, 2, 9‬‬ ‫‪9 ,8 ,6 ,2‬‬

‫نحوه ادغام‬

‫‪ ):Result‬آرایه کمکی(‬

‫‪,2 ,4 ,5 ,6 ,8 ,9 ,10 12‬‬

‫‪12 ,10 ,5 ,4‬‬

‫‪12 ,10 ,5 ,4‬‬ ‫‪9 ,8 ,6 ,2‬‬

‫‪18‬‬

‫مرتب سازی با ادغام‬ ‫‪‬‬

‫نحوه مرتب کردن هر‬ ‫یک از نیم آرایه ها‬ ‫تقسیم مساله به‬ ‫زیرمسائل‬

‫‪‬‬

‫حل زیر مسائل ساده‬

‫‪‬‬

‫ادغام نتایج زیرمسائل‬

‫‪‬‬

‫‪12 ,4 ,5 ,10‬‬ ‫‪5 ,10‬‬

‫‪12 ,4‬‬ ‫‪4‬‬

‫‪12‬‬ ‫‪12 ,4‬‬

‫‪10‬‬

‫‪5‬‬

‫‪10 ,5‬‬

‫‪12 ,10 ,5 ,4‬‬ ‫‪19‬‬

‫مرتب سازی با ادغام‬ void mergeSort(int low, int high) { if(low>=high) return; else{ mid = (low + high) / 2; mergeSort(low, mid); mergeSort(mid+1, high); merge(low, mid, high); } (mergeSort(0, n-1 ‫فراخوانی اولیه بصورت‬ } 20

‫مرتب سازی با ادغام‬ ‫{ )‪void merge(int low, int mid, int high‬‬ ‫اشاره گر به محل خواندن از نیم آرایه سمت چپ‪p1 = low;//‬‬ ‫اشاره گر به محل خواندن از نیم آرایه راست ‪p2 = mid+1;//‬‬ ‫اشاره گر به محل نوشتن در آرایه کمکی ‪p3 = low;//‬‬ ‫{ )‪while (p1 <= mid && p2<=high‬‬ ‫{ )]‪if (A[p1] <= A[p2‬‬ ‫;]‪B[p3] = A[p1‬‬ ‫;‪p1++‬‬ ‫;‪p3++‬‬ ‫{ ‪} else‬‬ ‫;]‪B[p3] = A[p2‬‬ ‫;‪p2++‬‬ ‫;‪P3++‬‬ ‫}‬ ‫}‬ ‫ادامه در صفحه بعد ‪//‬‬

‫‪21‬‬

‫مرتب سازی با ادغام‬ while(p1<=mid) { B[p3] = A[p1]; p1++; p3++; } while(p2<=high) { B[p3] = A[p2]; p2++; p3++; } } 22

‫مرتب سازی با ادغام‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی الگوریتم ‪mergeSort‬‬ ‫ورودی‪ :‬آرایه ‪A‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر ‪ A‬که آن را با ‪ n‬نمایش‬ ‫می دهیم‪.‬‬ ‫عمل کلیدی‪ :‬عمل نصف کردن آرایه )محاسبه ‪(mid‬‬ ‫تابع پیچیدگی‪:‬‬ ‫)‪T(n) = 1 + T(n/2) + T(n/2) + Tmerge (n‬‬ ‫‪= 2 T(n/2) + Tmerge (n) + 1‬‬

‫‪‬‬

‫پس ابتدا باید الگوریتم ‪ merge‬را تحلیل کنیم‪.‬‬ ‫‪23‬‬

‫مرتب سازی با ادغام‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی الگوریتم ‪merge‬‬ ‫ورودی‪ :‬دو آرایه مرتب شده که باید با هم‬ ‫ادغام شوند‪.‬‬ ‫اندازه ورودی‪ :‬مجموع تعداد عناصر دو آرایه‬ ‫عمل کلیدی‪ :‬افزایش اشاره گرها‬ ‫تابع پیچیدگی‬ ‫)‪T(n) = n  T(n)=O(n‬‬

‫‪24‬‬

‫مرتب سازی با ادغام‬ mergeSort ‫ادامه محاسبه مرتبه زمانی الگوریتم‬ T(n) = 2 T(n/2) + Tmerge (n) + 1 = 2 T(n/2) + n + 1 = 2 (2T(n/4) + n/2 + 1) + n + 1 = 4T(n/4) + 2n+ 3 = 2kT(n/2k) + kn + 2k -1 T(2) = 3 n/2k = 2  k = logn2 – 1 T(n) = n + nlogn – 1  T(n) = O(n logn)

25



‫مرتب سازی با ادغام‬ ‫‪‬‬

‫یک عیب‪ :‬استفاده از آرایه کمکی ‪B ‬‬ ‫افزایش مصرف حافظه‬

‫‪26‬‬

‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪27‬‬

‫توان رسانی‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه ‪ Xn (n‬عدد صحیح مثبت(‬ ‫راه حل واضح‪ x :‬را ‪ n-1‬مرتبه در خودش ضرب‬ ‫کن‪.‬‬ ‫‪Xn = X*X*X*…*X‬‬ ‫‪n‬مرتبه‬

‫‪‬‬

‫‪‬‬

‫این الگوریتم خطی می باشد یعنی مرتبه‬ ‫زمانی آن ‪ (O(n‬است‪.‬‬ ‫حل ‪x n/2‬‬ ‫تقسیم*و‪* x n/2‬‬ ‫‪x‬‬ ‫‪n is‬‬ ‫راه حل مبتنی بر ‪odd‬‬ ‫روش‬

‫‪n is even‬‬

‫‪X =  n/2 n/2‬‬ ‫‪x * x‬‬ ‫‪n‬‬

‫‪28‬‬

‫توان رسانی‬ int xToN(int x, int n) { if(n==1) return x; temp = xToN(x, n/2); if (n%2) return temp*temp*x; else return temp*temp; }

29

‫توان رسانی‬ ‫‪ ‬محاسبه مرتبه زمانی‬ ‫‪ ‬ورودی‪ :‬اعداد ‪ X‬و ‪n‬‬ ‫‪ ‬اندازه وردی‪ :‬مقدار عدد ‪n‬‬ ‫‪ ‬عمل کلیدی‪ :‬عمل ضرب‬ ‫‪ ‬تابع پیچیدگی‪:‬‬ ‫‪ n‬زوج باشد ‪ T(n) = T(n/2) + 1‬‬ ‫‪ n‬فرد باشد ‪ T(n) = T(n/2) + 2‬‬ ‫)‪T(n) = T(n/2) + 2 = T(n/4) + 2 + 2= T(n/4‬‬ ‫‪+4‬‬ ‫… = ‪= T(n/8) + 6 = T(n/16) + 8‬‬ ‫‪30‬‬

‫توان رسانی‬ T(n) = T(n/2k) + 2k T(n) = 2 logn2 T(1) = 0 n/2k = 1  k = logn2 T(n) = O(logn) ‫مرتبه زمانی لگاریتمی‬

31

‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪32‬‬

‫یافتن بزرگترین و کوچکترین عنصر‬ ‫الگوریتم ابتدایی‬ void maxMin(int n) { max = A[0]; min = A[0]; for(i=1; i max) max = A[i]; } } 33



‫یافتن بزرگترین و کوچکترین عنصر‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫ورودی‪ :‬آرایه ‪A‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر آرایه ‪A‬‬ ‫عمل کلیدی‪ :‬عمل مقایسه‬ ‫تابع پیچیدگی‬ ‫)‪W(n) = 2 (n-1)  W(n) = O(n‬‬

‫‪‬‬

‫مرتبه زمانی الگوریتم خطی می باشد‪.‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪34‬‬

‫یافتن بزرگترین و کوچکترین عنصر‬ ‫الگوریتم مبتنی بر روش تقسیم و حل‬ void maxMin(int low, int high, int &max, int &min) { if(low == high) { // there is only 1 element max = min = A[low]; } else if (high-low == 1) { //there are 2 elements if(A[low] > A[high]) { max = A[low]; min=A[high]; } else { max = A[high]; min=A[low]; } }else { mid = (low + high) / 2; maxMin(low, mid, max1, min1); maxMin(mid+1, high, max2, min2); max = (max1 > max2) ? max1 : max2; min = (min1 < min2) ? min1 : min2; }} 35



‫یافتن بزرگترین و کوچکترین عنصر‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫ورودی‪ :‬آرایه ‪A‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر آرایه ‪A‬‬ ‫عمل کلیدی‪ :‬عمل مقایسه‬ ‫تابع پیچیدگی‬ ‫‪W(n) = 2W(n/2) + 2‬‬ ‫‪W(n) = (3/2) n – 2‬‬ ‫‪W(2) = 1‬‬ ‫)‪ W(n)=O(n‬‬

‫‪‬‬

‫هر دو الگوریتم خطی اند اما الگوریتم دوم‬ ‫تعداد مقایسه کمتری دارد‪.‬‬ ‫‪36‬‬

‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪37‬‬

‫ضرب ماتریسها به روش استراسن‬ 

Cm1,m3 = Am1,m2 * Bm2,m3 ‫الگوریتم ابتدایی‬

void mult(int m1, int m2, int m3) { for(i=0; i<m1; i++) for(j=0; j<m2; j++) { C[i][j] = 0; for(k=0;k<m3;k++) C[i][j] = C[i][j] + A[i][k] * B[k][j]; } } } 38



‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫ورودی‪ :‬ماتریس های ‪ A‬و ‪B‬‬ ‫اندازه ورودی‪ :‬پارامترهای ‪ m1‬و ‪ m2‬و ‪m3‬‬ ‫که با ‪ i‬و ‪ j‬و ‪ k‬نمایش می دهیم‬ ‫عمل کلیدی‪ :‬عمل ضرب‬ ‫تابع پیچیدگی‬ ‫‪ T(i, j, k) = i*j*k‬‬ ‫اگر ماتریسها را ‪ n*n‬در نظر بگیریم ‪ ‬مرتبه‬ ‫زمانی الگوریتم ‪ (O(n3‬خواهد بود‪.‬‬ ‫‪39‬‬

‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫الگوریتم مبتنی بر روش تقسیم و حل‬ ‫فرض می کنیم ‪ n=2i‬باشد‪.‬‬ ‫هر ماتریس را به چهار ماتریس تقسیم می کنیم و بر‬ ‫کنیم‪.‬‬ ‫‪C1,2  A1,1‬‬ ‫می ‪A1,2 ‬‬ ‫طبق رابطه‪B1,2 ‬‬ ‫‪C1,1‬‬ ‫زیر عمل‪B1,1‬‬

‫‪‬‬ ‫‪B2,2 ‬‬

‫‪‬‬ ‫‪=‬‬ ‫‪*‬‬ ‫‪C 2,2  A 2,1‬‬ ‫‪A 2,2  B2,1‬‬ ‫‪C 2,1‬‬ ‫‪C1,1 = A1,1 * B1,1 + A1,2 * B2,1‬‬ ‫‪C1,2 = A1,1 * B1,2 + A1,2 * B2,2‬‬

‫دقت شود که ‪ Ai,j‬و ‪ Bi,j‬و ‪ Ci,j‬ها‬ ‫در این رابطه خود ماتریس‬ ‫هستند‪.‬‬

‫‪C 2,1 = A 2,1 * B1,1 + A 2,2 * B2,1‬‬ ‫‪C 2,2 = A 2,1 * B1,2 + A 2,2 * B2,2‬‬ ‫‪40‬‬

‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬

‫محاسبه مرتبه زمانی این الگوریتم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫ورودی‪ :‬دو ماتریس ‪ A‬و ‪B‬‬ ‫اندازه ورودی‪ :‬پارامتر ‪) n‬تعداد سطرها یا ستونهای‬ ‫ماتریس ها(‬ ‫عمل کلیدی‪ :‬ضرب )هزینه ضرب ها بیش از هزینه جمع‬ ‫است(‬ ‫تابع پیچیدگی‬

‫‪T(n)=n3‬‬

‫)‪ T(n)=O(n3‬‬ ‫‪‬‬

‫)‪T(n) = 8T(n/2‬‬ ‫‪T(1) = 1‬‬

‫‪‬‬ ‫‪‬‬

‫مرتبه زمانی این الگوریتم هم درجه ‪ 3‬می باشد‪.‬‬ ‫‪41‬‬

‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬

‫روش استراسن‪ :‬در واقع با ارائه فرمولهای‬ ‫جدیدی‪ ،‬الگوریتم قبل را بهبود داد )این الگوریتم‬ ‫هم مبتنی بر تقسیم و حل می باشد(‬ ‫) ‪T1 = (A1,2 – A2,2 ) * (B2,1 – B2,2‬‬ ‫) ‪T2 = (A1,1 + A2,2 ) * (B1,1 + B2,2‬‬ ‫) ‪T3 = (A1,1 – A2,1 ) * (B1,1 + B1,2‬‬

‫‪C1,1 = T1 + T2 – T4 +‬‬ ‫‪T6‬‬ ‫‪C1,2 = T4 + T5‬‬ ‫‪C2,1 = T6 + T7‬‬ ‫– ‪= T2 – T3 + T5‬‬

‫‪C‬‬

‫‪T4 = (A1,1 + A1,2 ) * B2,2‬‬ ‫) ‪T5 = A1,1 * (B1,2 – B2,2‬‬ ‫) ‪T6 = A2,2 * (B2,1 – B1,1‬‬ ‫‪T7 = (A2,1 + A2,2 ) * B1,1‬‬ ‫‪42‬‬

‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬

‫‪‬‬

‫در روابط مورد استفاده در روش قبل‪8 ،‬‬ ‫عمل ضرب و ‪ 4‬عمل جمع وجود داشت‪.‬‬ ‫در روابط مورد استفاده در روش استراسن‪،‬‬ ‫‪ 7‬عمل ضرب و ‪ 18‬عمل جمع و تفریق وجود‬ ‫دارد‪.‬‬

‫‪43‬‬

‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫ورودی‪ :‬دو ماتریس ‪ A‬و ‪B‬‬ ‫اندازه ورودی‪ :‬پارامتر ‪) n‬تعداد سطرها یا‬ ‫ستونهای ماتریس ها(‬ ‫عمل کلیدی‪ :‬ضرب‬ ‫تابع پیچیدگی‬ ‫)‪T(n) = 7 T(n/2‬‬ ‫‪T(1) = 1‬‬ ‫‪ T(n)=O(nx), x = log72‬‬ ‫) ‪ T(n) = O(n2.81‬‬ ‫الگوریتم استراسن‪ ،‬در عمل‪ ،‬بمراتب سریعتر از‬ ‫الگوریتم قبل است )برای ‪ n‬های بزرگ(‪.‬‬

‫‪‬‬ ‫‪‬‬

‫‪44‬‬

‫ضرب ماتریسها به روش استراسن‬ ‫‪‬‬

‫چند مورد قابل بحث‬ ‫‪‬‬

‫آیا واقعا تعداد زیاد جمع و تفریق ها در مقایسه با عمل‬ ‫ضرب‪ ،‬قابل چشمپوشی است و تاثیری ندارد؟ اگر عمل‬ ‫کلیدی را جمع یا تفریق در نظر بگیریم چه می شود؟‬

‫‪T(n) = 7T(n/2) + 18(n/2)2‬‬ ‫‪T(1) = 0‬‬ ‫) ‪ T(n)=O(nx), x = log72  T(n) = O(n2.81‬‬ ‫‪‬‬

‫اگر شرط ‪ n=2i‬برقرار نبود چه؟‬

‫‪45‬‬

‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫جستجوی دودویی )‪(binary search‬‬ ‫مرتب سازی با ادغام )‪(merge sort‬‬ ‫توان رسانی‬ ‫یافتن بزرگترین و کوچکترین عنصر‬ ‫ضرب ماتریس ها به روش استراسن‬ ‫مرتب سازی سریع )‪(quick sort‬‬

‫‪46‬‬

‫مرتب سازی سریع‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫ایده اصلی‪ :‬یکی از عناصر آرایه را بطور تصادفی انتخاب‬ ‫می کنیم )عنصر محوری( و داده ها را بر اساس آن به دو‬ ‫دسته کوچکتر و بزرگتر تقسیم می کنیم‪ .‬داده های کوچکتر‬ ‫از عنصر محوری را به سمت چپ عنصر محوری‪ ،‬و داده‬ ‫های بزرگتر از عنصر محوری را به سمت راست آن منتقل‬ ‫می کنیم‪ .‬سپس با همین روش داده های هر دو دسته را‬ ‫نیز مرتب می کنیم‪.‬‬ ‫در پایان هر مرحله‪ ،‬مکان عنصر محوری در آرایه مرتب‬ ‫شده نهایی مشخص می شود‪.‬‬ ‫در عمل می توانیم بجای انتخاب تصادفی عنصر محوری‪،‬‬ ‫عنصر اول را بعنوان عنصر محوری انتخاب کنیم‪.‬‬

‫‪47‬‬

‫مرتب سازی سریع‬ ‫‪‬‬

‫‪‬‬

‫یکی از پرطرفدارترین الگوریتم های مرتب‬ ‫سازی‬ ‫مزیت اصلی‪ :‬مرتبه زمانی حالت متوسط‬ ‫الگوریتم‬

‫‪48‬‬

‫مرتب سازی سریع‬ ‫‪‬‬

‫عنصر‬ ‫محوری‬

‫مثال‬

‫‪9 ,2 ,6 ,8 ,12 ,4 ,5 ,10‬‬

‫آرایه مرتب شده‬

‫‪12 ,10 ,9 ,2 ,6 ,8 ,4 ,5‬‬

‫‪12 ,10 ,9 ,8 ,6 ,5 ,4 ,2‬‬ ‫‪9 , 2 ,6 , 8 ,4 , 5‬‬

‫‪9 , 6 ,8 , 5 , 2 ,4‬‬

‫‪49‬‬

‫مرتب سازی سریع‬ ‫{ )‪void quickSort(int low, int high‬‬ ‫;‪if ( low >= high) return‬‬ ‫;)‪pivotPlace = partition(low, high+1‬‬ ‫;)‪quickSort(low, pivotPlace-1‬‬ ‫;)‪quickSort(pivotPlace+1, high‬‬ ‫}‬ ‫‪‬‬

‫‪‬‬

‫تابع ‪ partition‬عنصر محوری را انتخاب کرده و‬ ‫عناصر را با توجه به آن به دو دسته تقسیم کرده و‬ ‫مکان نهایی عنصر محوری را بر می گرداند‪.‬‬ ‫در مرتب سازی سریع نیز‪ ،‬نیازی به ترکیب یا ادغام‬ ‫جواب زیرمسائل نمی باشد‪.‬‬ ‫‪50‬‬

‫مرتب سازی سریع‬ ‫‪‬‬

‫مثال‬ ‫‪45, 25, 70, 96, 40, 12, 45, 20, 80, b‬‬

‫‪51‬‬

‫مرتب سازی سریع‬ int partition(int low, int high) { pivot = A[low]; p1 = low; p2 = high; while( p1 < p2) { do p1++ while(A[p1]pivot); if( p1 < p2) swap(A[p1] , A[p2]); } swap(A[low] , A[p2]); return p2; } 52

‫مرتب سازی سریع‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫ورودی‪ :‬آرایه ‪A‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر آرایه ‪A‬‬ ‫عمل کلیدی‪ :‬عمل مقایسه )در تابع ‪(partition‬‬ ‫تابع پیچیدگی‬ ‫‪‬‬

‫بدترین حالت برای الگوریتم مرتب سازی سریع زمانی‬ ‫اتفاق می افتد که داده ها از ابتدا مرتب باشند‪ .‬چرا؟‬

‫)‪(n) + W(n-1‬‬ ‫‪‬‬

‫‪W(n) = Tpartition‬‬

‫‪‬‬

‫پس ابتدا باید تابع پیچیدگی مربوط به الگوریتم‬ ‫‪ partition‬را مشخص کنیم‪.‬‬ ‫‪53‬‬

‫مرتب سازی سریع‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی الگوریتم ‪partition‬‬ ‫ورودی‪ :‬یک زیر آرایه از ‪A‬‬ ‫اندازه ورودی‪ :‬تعداد عناصر زیرآرایه‬ ‫عمل کلیدی‪ :‬عمل مقایسه‬ ‫تابع پیچیدگی‬ ‫)‪Tpartition(n) = n + 1  Tpartition(n)=O(n‬‬

‫‪‬‬

‫‪54‬‬

‫مرتب سازی سریع‬ ‫‪‬‬

‫‪‬‬

‫ادامه محاسبه مرتبه زمانی الگوریتم مرتب‬ ‫سازی سریع‬ ‫)‪W(n) = n+1 + W(n-1‬‬ ‫)‪ W(n) = O(n2‬‬ ‫اعتبار این الگوریتم بواسطه مرتبه زمانی‬ ‫حالت متوسط آن می باشد‪.‬‬

‫‪‬‬

‫‪55‬‬

‫مرتب سازی سریع‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی بهترین حالت‬ ‫تابع پیچیدگی‬ ‫)‪B(n) = n+1 + 2B(n/2‬‬ ‫)‪ B(n) = O(n logn‬‬

‫‪56‬‬

‫مرتب سازی سریع‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی حالت متوسط‬ ‫تابع پیچیدگی‬

‫‪1 n‬‬ ‫‪‬‬ ‫‪A(n) =  ∑ n + 1 + A(k − 1) + A(n − k ) ‬‬ ‫‪n  k =1‬‬ ‫‪‬‬ ‫)‪ A(n) = O(n logn‬‬

‫‪57‬‬