تحلیل پیچیدگی زمانی الگوریتم ها در متلب

صفحه 1:


صفحه 2:
مثالی از یک الگوریتم در متلب الگوریتم جستجوی ترتیبی ‎function [location] = SeqSearch(A,x)‏ ‎len=length(A);‏ ‎location=0;‏ ‎for i=1:len‏ ‎if A(i)==x‏ ‎location=i;‏ ‎break;‏ ‎end‏ ‎end‏ ‎end‏ 

صفحه 3:
تحلیل پیچیدگی زمانی الگوربتم‌ها عیازت آننث از #تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می‌شود. #انتخاب عمل | اساس تجربه صورت می‌پذبرد. ‎)١‏ ييجيدكى زمانى الكوريتم در حالت معمول مانند ضرب ‎Conk = Aman ® Bnxk este‏ ‎T(m,n,k)=mxnxk‏ ‏و یا برای سادگی میگوییم: ۲)0(<3" ‎ ‎ ‎ 

صفحه 4:
تحلیل پیچیدگی زمانی الگوریتم‌ها ۲) پیچیدگی زمانی الگوربتم در بدترین حالت مانند جستجوی ترتیبی ‎W(n)=n‏ ‏۳) پیچیدگی زمانی الگوریتم در بهتربن حالت مانند جستجوی ترتیبی B(n)=1 

صفحه 5:
تحلیل پیچیدگی زمانی الگوریتم‌ها ۴ پیچیدگی زمانی الگوربتم در حالت میانگین توجه: یک مقدار ميانكين را فقط زمانی می‌توان معمولی خواند که حالتهای واقعی از میانگین انحراف زیادی نداشته باشد. مثال: جستجوی ترتیبی حالت ۱: لا همواره در آرایه هست 5 8 A(n)= (0 Lt Shad eer) ‏اكات‎ ‏م2‎ 3 n> eet n* 2 2 

صفحه 6:
تحلیل پیچیدگی زمانی الگوریتم‌ها حالت ۲: ا ممکن است در آرایه نباشد. احتمال وجود 6 را در آرایه ۵ درنظر می‌گیریم. ‎nm‏ ‎A(n)= S7(kx? )+n (1 -p)‏ ‎k=1 n‏ _ Py n(n+)) = 2 - 1, ‏الله‎ 1 ۰ )1-2( + NID 

صفحه 7:
تحلیل پیچیدگی زمانی الگوریتم‌ها در تحلیل پیچیدگی الگوریتم‌هاء پیچیدگی حافظه نیز قابل بحث است 

صفحه 8:
مرتبه الگوریتم در بسیاری از موارد نیاز است تا دو الگوریتم را با هم مقايسه كنيم ... تابع پیچیدگی آنها را (زمانی/حافظه) را بدست می‌آوریم ولی ... از آنجایی که داشتن درک صحیحی از مقایسه دو تابع پیچیدگی در يسيارئ از موارد مشكل است» ... ثیاز است تا توایع پیچیدگی را به شکل‌های ساده‌تری بیان کنیم. پیچیدگی الگوریتم‌ها با مرتبه پیچیدگی که بگی است کار مقایسه دو الگوریم را أز ‎1S cual gy cal‏ شکل ساده‌ای از توابع آسان می‌کند. 

صفحه 9:
مرتبه الگوربتم در پاره‌ای از موارد رسیدن به تابع ب پیچیده‌ای است ولی ... می‌توانيم شکل ساده‌ای از آن را که بیان کننده پیچیدگی مساله باشد را بدست آوریم. گی با داشتن الگوریتم کار 

صفحه 10:
مرتبه الگوریتم تعریف 60 ) برای یک تابع پیچیدگی مفروض ‎nos. F(n)‏ ۱۰09 مجموعه‌ای از تابع پیچیدگی ( 61 ۵ است که برای آنها به ازای یک ثابت حقیقی مثبت > آنكاه يى عدد صحيح غير منفى ال وجود دارد به قسمی که به ازای همه ‎g(n) =cxf(n).).n=N‏ روش نمايش: ‎g(n) € O(f(N))‏ 

صفحه 11:
مرتبه الگوریتم نمایش به صورت دیاگرام: ofa) gn) وس N (a) g(n) € O(f(n)) 

صفحه 12:
د) مرتبه الگوریتم در این شکل هرچند 10 + ‎M‏ در ابتدا مقادیری بیشتر از 2/7 دارند ولی برای 10< > روند دیگری شکل می‌گیرد. جم 5 4 101112 9 8 7 6 5 4 3 2 1 

صفحه 13:
مرتبه الگوریتم ۶ هه مرو ‎for n< 5n? < 5n?,‏ ‎c=5andN=0 Vv‏ m+10ne Or) ? for n= 'n? + 10n < n? + 10n? = 11n?, c=llandN=1 5 2 1۵ > بر( 7۴ بخ < 0 ۲0۲ 1 1 < ۸ 200 1 <عء 

صفحه 14:
مرتبه الگوریتم (a) O(n?) 

صفحه 15:
مرتبه الگوریتم تعریف ‎Q (Omega)‏ برای یک تابع پیچیدگی مفروض ( 13) : مانند ۸ 0.۱۵9 مجموعه‌ای از توابع پیچیدگی ‎ot GUN)‏ که برای آنها به ازای یک ثابت حقیقی مثبت > آنگاه یک عدد صحيح غير منفى لا وجود دارد به قسمی که به ازای عمه ‎g(n) =cxXF(N) ..nEN‏ روش نمایش: )6266 6 (9)۳ 

صفحه 16:
مرتبه الگوریتم نمایش به صورت دیاگرام: )0( 800( > 2 )70(( 

صفحه 17:
مرتبه الگوریتم ‎m+10neQ(r)?‏ ‎for N= n?+10n>n’,‏ ‎c=landN=0 V‏ meQ(r) ۶ For n= n>1xn?, c=landN=1 V 

صفحه 18:
مرتبه الگوریتم 4n3 + 3n2 4 6n® + nr 2"+4n (b) Q@) 

صفحه 19:
مرتبه الگوریتم ‎(Theta) 45‏ © بای یک تابع پیچیدگی مفروض ‎nelog masts FCN)‏ مجموعه‌ای از توابع پیچیدگی ‎g(n)‏ است که برای آنها به ازای ثابت‌های حقیقی مثبت 6 و 0 ‏آنگاه یک عدد صحیح غیر منفی لا] وجود دارد به قسمی که به ازای همه ‎ed NEN‏ ‎dxf(n) =g(n) =cxf(n) 9)۳( 6 0)۴)۳(( ‏روش نمایش:‎ ‎ ‎ 

صفحه 20:
مرتبه الگوریتم به عبارتی دیگر: g(n) € O(f(n)) AND Q(f(n) ‏يعنى:‎ O(F (n)) = O(F (n)) NQ(F (n)). 

صفحه 21:
مرتبه الگوربتم نمایش به‌صورت دیاگرام: ‎df(n)‏ g(a) cf) ص سس N (c) gar) € OC ftn)) ‏نمایش به‌صورت مجموعه‌ای:‎ | OCF (n)) = O(F (2) ۱ )۴ )0(۰ 

صفحه 22:
مرتبه الگوریتم 9 تسوه 002۵ < 062 (0) 

صفحه 23:
مرتبه الگوریتم ويزكيهاى 0 ‎١‏ - اكر (0)11 بتواند به صورت مجموع تعداد محدودى از توايع ديكر نوشته شود. »در لين صورت أن ن تابعی که بیشترین رشد را دارد. 0 را ‎f(n)=9logn+5(log ‏)رم‎ ‎2n3e€O(n3) ‎5 ‎f(n)€ O(n?) ‎ ‎ 

صفحه 24:
مرتبه الگوریتم ده ویزگیهای (6: ۲- ویژگی ضرب اگر (:9:60)6 و (9260)6 در آن صورت: 7 € .9:9 ‎O(f,f,)‏ er Set ‏كر () © 9126 و (و)0 926 در آن صورت:‎ ? © :9,9 ‎O(f,+f,)‏ ‏۴- ویژگی ضرب در مقدار ثابت اگر (9601 در آن صورت: ‎kg € ?‏ ‎O(f)‏ 

صفحه 25:
مرتبه الگوریتم ادامه ويزكيهاى ‎O‏ ۵- می‌توان () را در بیان پیچیدگی محاسباتی نیز آورد ‎T(n)=O(n2)+55n3+2n+10 x.‏ در این الگوریتم ابتدا مرتب‌سازی انجام می‌پذیرد و سپس کار ادامه می‌یابد 

صفحه 26:
مرتبه الگوریتم ویژگی های مرتبه: 1-g (n) € O(Ff)n)) if and only if ‏لدگر و تنهندگر)‎ F(n) € Q(g(n)) 2- g(n) € © (f{n)) if and only if Anje O(g(n)) 3-1۲ b> land a>1,thenlog, ne © (log, (۰ این ویژگی نشان می‌دهد که تمامی تابع‌ها لگاریتمی در یک گروه پیچیدگی مشترک قرار ذارند. اين كروه در ادامه اين درس با (3/ [© 1 ) © مشخص مىشود. 

صفحه 27:
مرتبه الگوربتم تعریف 0) برای یک تابع پیچیدگی مفروض ( 13 )4 مانند ۳ ۰۱۵9, مجموعه‌ای از توابع پیچیدگی ( ۴۷ ۵ است که برای آنها 0 و به ازای ثابت حقیقی مثبت ) ] به قسمى که به ای سبه 2۷ درم )۷۴ ک ‎g(n)‏ ‏روش نمایش: (0)۴)۳ 6 (9)۳ 

صفحه 28:
مرتبه الگوریتم ویژگی های مرتبه: 4-1۴ 0 < a>0,a" € 0(b") .. ‏این ویژگی نشان می‌دهد که‎ برخلاف توابع پیچیدگی لگاریتمی. توابع پیچیدگی نمایی در یک گروه پیچیدگی قرارندارند. 5- For all aia" € o(n!). ... ‏این ویفگی نشان می‌دهد که‎ ‏تابع پیچیدگی ۱! از هر تابع پیچیدگی نمایی بدتر است.‎ 

صفحه 29:
مرتبه الگوریتم ویژگی های مرتبه: فزقیب گزوه‌ها پیچی کی زیر زا از چپ بفاراسة:ذرنظر يكيرية:-ه Ollgn) O(n) OM ign) O(n’) OC) OCF) O@") BH) O(n), k>jand b> a>1. ‎O(N) Sarge: Gb agile‏ در كروهى سمت جب گروهی که تابع ييجيدكى (1)11 در آن قرار دارد باشد در اين صورت: ‎o(f (n)).‏ € () و ‎ ‎ ‎ 

صفحه 30:
مروری بر روش‌های اثبات (Direct Prooh. ‏برهان‎ ) در برهان مستقیم. نتیجه از ترکیب منطقی اصل‌هاء تعریف‌ها و تئوری‌های پیشین بدست می‌آید. بطور مثال برهان مستقیم برای اثبات زوج بودن جمع دو عدد زوج بکار می‌رود: برای هر ۲ عدد زوج صحیح ۸ و لآ می‌توانیم بنویسیم 222 5 ‎YH=2D‏ ‏جمع ((۵6۷-(+۲2+۲-۲)۵ نیز طبق تعریف عددی زوج است. بنابراین جمع دو عدد زوج همواره زوج می‌باشد. 

صفحه 31:
مروری بر روش‌های اثبات (Proof by ۱۵0۵010< ‏اثبات استقرایی‎ )۲ در اثبات استقرایی. ابتدا یک «حالت پایه» اثبات می‌شود. سپس به کمک «فرض استقراء» مجموعه‌ای از حالات بعدی اثبات می‌شود که اصطلاحا «گام استقرا» گفته می‌شود. از آنجایی که حالت پایه صحیح است. حالات دیگر بعدی هم با گام استقرا نشان‌داده می‌شود که صحیح هستند. حتی اگر همه آنها هم نتوانند به خاطر تعداد نا متناهیشان به صورت مستقیم اثبات شوند. 

صفحه 32:
مروری بر روش‌های اثبات Proof by reductio adja ‏اثبات با بر هان‎ ۳ (absurdum در اثبات با برهان خلف. فرض می‌کنیم گزاره‌ای غلط است. سپس به یک تناقض منطقی می‌رسیم. پس نتیجه می‌گیریم که آن گزاره باید صحیح باشد. این روش یکی از متداول‌ترین روش‌های اثبات در ریاضی است. ۴ اثبات از طریق ترانهش ‎(Proof by Transpositiony‏ اثبات از طریق ترانهش نتیجه «اگر ۵0 آنگاه 4 را به وسیله اثبات گزاره «گر نقیض 4 آنگاه نقیض /» برقرار می‌سازد. و اثبات از طریق شبیه سازی, اثبات فرسایشی. اثبات احتمالاتی» اثبات ترکیبیاتی. اثبات غیر تمثیلی و اثبات ابتدایی 

صفحه 33:
مرتبه الگوریتم چنانچه ((700) 0 © (9)71 آنگاه g(n) € O(f (n)) -Q(f (n)). ... ‏این بدان معنا است که‎ (9)0 عضو مجموعه (((/2)۴۲) لسنولی.. عضو ((2)۴/7ک نمی‌باشد. 

صفحه 34:
مرتبه الگوریتم قضیه: چنانچه ((70) 0 (9)70 باشد آنگاه ‎g(n) € O(f(n))-2‏ ‎n,‏ اثبات: به دلیل آنکه (()9)0(>0 .. برای هر عدد مثبت حقیقی ۷ .> ای ‎a(n) Sex Fin), Sebo‏ بس وقتی برای هر اين رابطه برقرار است پس 6 ای وجود دارد که .... a(n) € O(F(n)). “alot (پس این بخش را با برهان مستقیم اثبات کردیم) 

صفحه 35:
مرتبه الگوریتم قضيه: جنانجه ((1]11) © © (9)17 باشد آنگاه 5۵-(()0)۴ > ()9 ‎n,‏ ‏در ادامه با برهان خلف نشان خواهیم داد که (9)1۱ عضو ((1/0) 62 نیست. چنانچه ((2)70؟ ‏ (9)/0 باشد در اینصورت ... در اینصورت ثابت حقیقی 0 < عو يلا/ ای وجود دارند که برای.(() ‎G(n) > eX‏ اما چون ((10) ۵ € ‎Un)‏ a(n) <5 x 0۰ 0 2 دارد كه به ازاى تمامى ‎NZ‏ هردوى اين معادلدها بايست براى تمامى ‎!١‏ بزركتر مساوى يلا/ ورلا/ برقرار باشد. اين تناقض نشان مىدهد كه (9]/7 نمىتواند عضو ((1]/7) 62 باشد. 

صفحه 36:
مرتبه الگوریتم g(n) € O(f(n))- ‏باشد آنگاه‎ g(n) 2 0 )۶0(( ‏قضیه: چنانچه‎ 2 (F(n)) آیا دو مجموعه ((10) 0 و ((/) 2 - ((6/0) 0۵ با هم یکسانند؟ خير توابعی هستند که عضو ((6/0) 62 - ((70/0) 0 هستند ولی عضو 0 مثال بعدی این مطلب را نشان می‌دهد. 

صفحه 37:
مرتبه الگورینم ویژگی های مرتبه: قضیه: lim on noo f (n 0 implies g(r) € o(f (n)) ¢ implies g(n)€O(f(n)) if e> 0 0 implies f (n) € o(g(n)) 

صفحه 38:
مرتبه الگوریتم (ny _ [implies g(n) € OF (n)) Hfe> 0 ‏ویژگی های مرتبه:‎ im, Fa =4 0 implies g(n) € o(f (n)) co implies f (n) € 0(g(n)) 2 2 n 3 . nf2_, 1 —E€Eo(n lm ——= lim —= >9)8( ‏جب رل چراکه‎ - im 5 = 0 

صفحه 39:
مرتبه الگوریتم ویژگی های مرتبه: tim 2) ‎F Gay =] 2 impos 9(n) € off (m))‏ سر ‎c implies g(n) € O(f (n)) ife >0 co implies f (n) € 0(g(n)) ‎thopital oct .. ‏در اين قاعده به جای انکه حد صورت بر مخرج را محاسبه کنیم‎ ‏حد مشتق صورت را بر مشتق مخرج بدست می آوریم.‎ ‏در این خصوص به قواعد مشتق كبري مراجعه فرماييد. ‎ ‎ ‎