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

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

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

اسلاید 2: تحلیل پیچیدگی زمانی الگوریتم‌هاعبارت است از تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می‌شود. انتخاب عمل اصلی بر اساس تجربه صورت می‌پذیرد1) پیچیدگی زمانی الگوریتم در حالت معمولمانند ضرب ماتریس: Cm×k=Am×n×Bn×kT(m,n,k)=m×n×kو یا برای سادگی میگوییم: T(n)=n3

اسلاید 3: تحلیل پیچیدگی زمانی الگوریتم‌ها2) پیچیدگی زمانی الگوریتم در بدترین حالتمانند جستجوی ترتیبیW(n)=n3) پیچیدگی زمانی الگوریتم در بهترین حالتمانند جستجوی ترتیبیB(n)=1

اسلاید 4: تحلیل پیچیدگی زمانی الگوریتم‌ها4) پیچیدگی زمانی الگوریتم در حالت میانگینتوجه: یک مقدار میانگین را فقط زمانی می‌توان معمولی خواند که حالتهای واقعی از میانگین انحراف زیادی نداشته باشد.مثال: جستجوی ترتیبیحالت 1: x همواره در آرایه هست

اسلاید 5: تحلیل پیچیدگی زمانی الگوریتم‌هاحالت 2: x ممکن است در آرایه نباشد. احتمال وجود x را در آرایه p درنظر می‌گیریم.

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

اسلاید 7: مرتبه الگوریتمدر بسیاری از موارد نیاز است تا دو الگوریتم را با هم مقایسه کنیم ...تابع پیچیدگی آنها را (زمانی/حافظه) را بدست می‌آوریم ولی ....از آنجایی‌که داشتن درک صحیحی از مقایسه دو تابع پیچیدگی در بسیاری از موارد مشکل است، ...نیاز است تا توابع پیچیدگی را به شکل‌های ساده‌تری بیان کنیم.از این رو است که بیان پیچیدگی الگوریتم‌ها با مرتبه پیچیدگی که شکل ساده‌ای از توابع پیچیدگی است، کار مقایسه دو الگوریم را آسان می‌کند.همچنین ...

اسلاید 8: مرتبه الگوریتمدر پاره‌ای از موارد رسیدن به تابع پیچیدگی با داشتن الگوریتم کار پیچیده‌ای است ولی ...می‌توانیم شکل ساده‌ای از آن را که بیان کننده پیچیدگی مساله باشد را بدست آوریم.

اسلاید 9: مرتبه الگوریتمتعریف O )برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n، مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها به ازای یک ثابت حقیقی مثبت c آنگاه یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه n≥N داریم g(n) ≤c×f(n)روش نمایش: g(n) ϵ O(f(n))

اسلاید 10: مرتبه الگوریتمنمایش به صورت دیاگرام:

اسلاید 11: د) مرتبه الگوریتمدر این شکل هرچند n2 + 10n در ابتدا مقادیری بیشتر از 2n2 دارند ولی برای n<=10 روند دیگری شکل می‌گیرد.

اسلاید 12: مرتبه الگوریتم5n2 ∊ O(n2) ?for n ≤ 0, c = 5 and N = 0 √n2 + 10n ∊ O(n2) ?for n ≥ 1,c = 11 and N = 1 √n ∊ (n 2) ?for n ≥ 1,c = 1 and N = 1 √

اسلاید 13: مرتبه الگوریتم

اسلاید 14: مرتبه الگوریتمتعریف Ω (Omega) برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها به ازای یک ثابت حقیقی مثبت c آنگاه یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه n≥N داریم g(n) ≥c×f(n)روش نمایش: g(n) ϵ Ω(f(n)

اسلاید 15: مرتبه الگوریتمنمایش به صورت دیاگرام:

اسلاید 16: مرتبه الگوریتمn2 + 10n ∊ Ω (n2) ?for n ≥ 0,c = 1 and N = 0 √n3 ∊ Ω(n2) ?For n ≥ 1,c = 1 and N = 1 √

اسلاید 17: مرتبه الگوریتم

اسلاید 18: مرتبه الگوریتمتعریف Θ (Theta) برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها به ازای ثابت‌های حقیقی مثبت c و dآنگاه یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه n≥N داریم: d×f(n) ≥g(n) ≥c×f(n)روش نمایش: g(n) ϵ Θ(f(n))

اسلاید 19: مرتبه الگوریتمبه عبارتی دیگر: g(n) ϵ O(f(n)) AND Ω(f(n)یعنی:

اسلاید 20: مرتبه الگوریتمنمایش به‌صورت دیاگرام:نمایش به‌صورت مجموعه‌ای:

اسلاید 21: مرتبه الگوریتم

اسلاید 22: مرتبه الگوریتمویژگیهای O:1- اگر g(n) بتواند به صورت مجموع تعداد محدودی از توابع دیگر نوشته شود، در این صورت آن تابعی که بیشترین رشد را دارد، O را مشخص می‌کندf(n)=9logn+5(log n)3+3n2+2n32n3ϵO(n3) f(n)ϵO(n3)

اسلاید 23: مرتبه الگوریتمادامه ویژگیهای O:2- ویژگی ضرباگر g1ϵO(f1) و g2ϵO(f2) در آن صورت:g1g2 ϵ ?O(f1f2)3- ویژگی جمعاگر g1ϵO(f1) و g2ϵO(f2) در آن صورت:g1+g2 ϵ ?O(f1+f2)4- ویژگی ضرب در مقدار ثابتاگر gϵO(f) در آن صورت: kg ϵ ?O(f)

اسلاید 24: مرتبه الگوریتمادامه ویژگیهای O:5- می‌توان O را در بیان پیچیدگی محاسباتی نیز آوردمثلا T(n)=O(n2)+55n3+2n+10در این الگوریتم ابتدا مرتب‌سازی انجام می‌پذیرد و سپس کار ادامه می‌یابد

اسلاید 25: مرتبه الگوریتمویژگی های مرتبه:1- g (n) ∊ O(f)n)) if and only if (اگر و تنها اگر)f(n) ∊ Ω(g(n))2- g(n) ∊ Θ (f(n)) if and only if f(n)∊ Θ(g(n))3- If b> 1 and a > 1, then loga n ∊ Θ (logb n).این ویژگی نشان می‌دهد که تمامی تابع‌ها لگاریتمی در یک گروه پیچیدگی مشترک قرار دارند.این گروه در ادامه این درس با Θ(lgn) مشخص می‌شود.

اسلاید 26: مرتبه الگوریتمتعریف o )برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n، مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها به ازای هر ثابت حقیقی مثبت c آنگاه یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه n≥N داریم g(n) ≤c×f(n)روش نمایش: g(n) ϵ o(f(n)

اسلاید 27: مرتبه الگوریتمویژگی های مرتبه:4-If b > a > 0, then این ویژگی نشان می‌دهد که ...برخلاف توابع پیچیدگی لگاریتمی، توابع پیچیدگی نمایی در یک گروه پیچیدگی قرارندارند.5- For all a > 0این ویژگی نشان می‌دهد که ...تابع پیچیدگی n! از هر تابع پیچیدگی نمایی بدتر است.

اسلاید 28: مرتبه الگوریتمویژگی های مرتبه:6- ترتیب گروه‌ها پیچیدگی زیر را از چپ به راست درنظر بگیرید ...k > j and b > a> 1. چنانچه تابع پیچیدگی g(n) در گروهی سمت چپ گروهی که تابع پیچیدگی f(n) در آن قرار دارد باشد در این صورت:

اسلاید 29: 1) برهان مستقیم (Direct Proof)در برهان مستقیم، نتیجه از ترکیب منطقی اصل‌ها، تعریف‌ها و تئوری‌های پیشین بدست می‌آید. بطور مثال برهان مستقیم برای اثبات زوج بودن جمع دو عدد زوج بکار می‌رود:برای هر ۲ عدد زوج صحیح x و y می‌توانیم بنویسیم x=2a و y=2b. جمع (x+y)=2a+2b=2(a+b) نیز طبق تعریف عددی زوج است. بنابراین جمع دو عدد زوج همواره زوج می‌باشد.مروری بر روش‌های اثبات

اسلاید 30: 2) اثبات استقرایی (Proof by Induction)در اثبات استقرایی، ابتدا یک «حالت پایه» اثبات می‌شود. سپس به کمک «فرض استقراء» مجموعه‌ای از حالات بعدی اثبات می‌شود که اصطلاحا «گام استقرا» گفته می‌شود. از آنجایی که حالت پایه صحیح است، حالات دیگر بعدی هم با گام استقرا نشان‌داده می‌شود که صحیح هستند، حتی اگر همه آنها هم نتوانند به خاطر تعداد نا متناهیشان به صورت مستقیم اثبات شوند.مروری بر روش‌های اثبات

اسلاید 31: 3) اثبات با بر هان خلف (Proof by reductio ad absurdum)در اثبات با برهان خلف، فرض می‌کنیم گزاره‌ای غلط است، سپس به یک تناقض منطقی می‌رسیم، پس نتیجه می‌گیریم که آن گزاره باید صحیح باشد. این روش یکی از متداول‌ترین روش‌های اثبات در ریاضی است.4) اثبات از طریق ترانهش (Proof by Transposition)اثبات از طریق ترانهش نتیجه «اگر p آنگاه q» را به وسیله اثبات گزاره «اگر نقیض q آنگاه نقیض p» برقرار می‌سازد.و اثبات از طریق شبیه سازی، اثبات فرسایشی، اثبات احتمالاتی، اثبات ترکیبیاتی، اثبات غیر تمثیلی و اثبات ابتداییمروری بر روش‌های اثبات

اسلاید 32: مرتبه الگوریتمقضیه:چنانچه g(n) ∊ o (f(n)) آنگاهاین بدان معنا است که ...g(n) عضو مجموعه O(f(n)) است ولی ...عضو Ω(f(n)) نمی‌باشد.

اسلاید 33: مرتبه الگوریتمقضیه: چنانچهg(n) ∊ o (f(n)) باشد آنگاه g(n) ∊ O(f(n))-Ω (f(n))اثبات:به دلیل آنکه g(n)∊o(f(n)) ...برای هر عدد مثبت حقیقی c، N ای وجود دارد که برای تمامی n>Nپس وقتی برای هر c این رابطه برقرار است پس c ای وجود دارد که .... بنابراین : (پس این بخش را با برهان مستقیم اثبات کردیم)

اسلاید 34: مرتبه الگوریتمقضیه: چنانچهg(n) ∊ o (f(n)) باشد آنگاه g(n) ∊ O(f(n))-Ω (f(n))در ادامه با برهان خلف نشان خواهیم داد که g(n) عضو Ω (f(n)) نیست.چنانچه g(n) ∊ Ω(f(n)) باشد در اینصورت ....در اینصورت ثابت حقیقی c > 0و N1 ای وجود دارند که برای تمامی n≥N1اما چون g(n) ∊ o (f(n)) هست پس N2 ای وجود دارد که به ازای تمامی n ≥ N2هردوی این معادله‌ها بایست برای تمامی n بزرگتر مساوی N1, N2 برقرار باشد.این تناقض نشان می‌دهد که g(n) نمی‌تواند عضو Ω (f(n)) باشد.

اسلاید 35: مرتبه الگوریتمقضیه: چنانچهg(n) ∊ o (f(n)) باشد آنگاه g(n) ∊ O(f(n))-Ω (f(n))آیا دو مجموعه o (f(n)) و O (f(n)) – Ω (f(n)) با هم یکسانند؟خیرتوابعی هستند که عضو O (f(n)) – Ω (f(n)) هستند ولی عضو o نیستند.مثال بعدی این مطلب را نشان می‌دهد.

اسلاید 36: مرتبه الگوریتمویژگی های مرتبه:قضیه:

اسلاید 37: مرتبه الگوریتمویژگی های مرتبه: چراکه

اسلاید 38: مرتبه الگوریتمویژگی های مرتبه:قاعده hopital:در این قاعده به جای انکه حد صورت بر مخرج را محاسبه کنیم ...حد مشتق صورت را بر مشتق مخرج بدست می آوریم.در این خصوص به قواعد مشتق‌گیری مراجعه فرمایید.