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


تحلیل الگوریتم ها(تحلیل در زبان متلب)

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

تحلیل پیچیدگی زمانی الگوریتم ها
عبارت است از
تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می شود.
انتخاب عمل اصلی بر اساس تجربه صورت می پذیرد

1) پیچیدگی زمانی الگوریتم در حالت معمول
مانند ضرب ماتریس: Cm×k=Am×n×Bn×k
T(m,n,k)=m×n×k
و یا برای سادگی میگوییم: T(n)=n3

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

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

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

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

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

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

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

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

مرتبه الگوریتم

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

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

مرتبه الگوریتم
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 √

مرتبه الگوریتم

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

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

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

n3 ∊ Ω(n2) ?
For n ≥ 1,
c = 1 and N = 1 √

مرتبه الگوریتم

مرتبه الگوریتم
تعریف Θ (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))

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

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

نمایش به صورت مجموعه ای:

مرتبه الگوریتم

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

2n3ϵO(n3)

f(n)ϵO(n3)

مرتبه الگوریتم
ادامه ویژگیهای 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)

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

مرتبه الگوریتم
ویژگی های مرتبه:
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) مشخص می شود.

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

مرتبه الگوریتم
ویژگی های مرتبه:
4-If b > a > 0, then
این ویژگی نشان می دهد که …
برخلاف توابع پیچیدگی لگاریتمی، توابع پیچیدگی نمایی در یک گروه پیچیدگی قرارندارند.

5- For all a > 0
این ویژگی نشان می دهد که …
تابع پیچیدگی n! از هر تابع پیچیدگی نمایی بدتر است.

مرتبه الگوریتم
ویژگی های مرتبه:
6- ترتیب گروه ها پیچیدگی زیر را از چپ به راست درنظر بگیرید …

k > j and b > a> 1.

چنانچه تابع پیچیدگی g(n) در گروهی سمت چپ گروهی که تابع پیچیدگی f(n) در آن قرار دارد باشد در این صورت:

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

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

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

مروری بر روش های اثبات

مرتبه الگوریتم
قضیه:
چنانچه g(n) ∊ o (f(n)) آنگاه

این بدان معنا است که …
g(n) عضو مجموعه O(f(n)) است ولی …
عضو Ω(f(n)) نمی باشد.

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

پس وقتی برای هر c این رابطه برقرار است پس c ای وجود دارد که ….
بنابراین :

(پس این بخش را با برهان مستقیم اثبات کردیم)

مرتبه الگوریتم
قضیه: چنانچه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)) باشد.

مرتبه الگوریتم
قضیه: چنانچه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 نیستند.
مثال بعدی این مطلب را نشان می دهد.

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

مرتبه الگوریتم
ویژگی های مرتبه:

چراکه

مرتبه الگوریتم
ویژگی های مرتبه:

قاعده hopital:
در این قاعده به جای انکه حد صورت بر مخرج را محاسبه کنیم …
حد مشتق صورت را بر مشتق مخرج بدست می آوریم.

در این خصوص به قواعد مشتق گیری مراجعه فرمایید.