پیچیدگی زمانی

[حمیدرضاصادقیان]

سلام دوستان.میخواستم در مورد محاسبه O در این تابع یک توضیح کامل بدید.


Function Test(n:integer):Integer;
Begin
if n=1 then test:=1;
Else Test:=2*Test(n/2)+1
End;

ممنون میشم روش محاسبه اش هم بیان کنید.

[whitehat]

من فكر مي كنم پيچيدگي آن log nاست ، بعدا در مورد محاسبه مي نويسم. چون هر دفعه بازه مورد نظر نصف ميشه ، از روي آن مي توانيد پيچيدگي را حدس بزنيد

[حمیدرضاصادقیان]

سلام.با تشکر من مشکلم در مورد پیدا کردن ثابت های c1,c2,n0 هستم .نمیدونم چطوری باید این عددها رو پیدا کنم؟

[MShirzadi]

n0 , c1 , c2 چی هسن یه کمی توضیح می دی

[حمیدرضاصادقیان]

در فرمول اصلی
O(g(n)) شما تابع زیر رو دارید


O(g(n))=f(n)= c1g(n)<=f(n)<=c2g(n) به ازای n>=n0

[Alireza_Salehi]

سلام.با تشکر من مشکلم در مورد پیدا کردن ثابت های c1,c2,n0 هستم .نمیدونم چطوری باید این عددها رو پیدا کنم؟
به سادگی !
کوچکترین عددهایی که در رابطه صدق کنه جواب هستند. (c1,c2)
n0 هم عددی است که از اون به بعد رابطه صدق میکنه.
محاسبه اینها تقریبا فرمول نداره!

این ها صرفا یک ضریب هستند و در بحث پیچیدگی زمانی ضرایب عددی رو در نظر نمی گیرند.

معمولا حدود 10 تا تابع معروف هستند که اکثر پیچیدگی ها به این ها گرد می شوند.

[delfi01]

سلام

جناب whitehat ممكنه در مورد روش بدست آوردن جوابتون توضيح بديد آخه جواب شما اثبات نميشه:متفکر:

اشكال استدلال من چيه؟
با توجه به شكل تابع ، فرمول T(n)=2T(n/2)+b بدست مي آيد.كه با استفاده از قضيه اصلي

ثابت مي شودT(n)=q(n) واين با حدس و استقرا ثابت مي شود.T(n)=O(n)

[whitehat]

سلام

جناب whitehat ممكنه در مورد روش بدست آوردن جوابتون توضيح بديد آخه جواب شما اثبات نميشه:متفکر:

اشكال استدلال من چيه؟
با توجه به شكل تابع ، فرمول T(n)=2T(n/2)+b بدست مي آيد.كه با استفاده از قضيه اصلي

ثابت مي شودT(n)=q(n) واين با حدس و استقرا ثابت مي شود.T(n)=O(n)

آیا ضریب 2 در پیچیدگی مسئله تاثیر دارد؟
فرض اشتباه باعث جواب اشتباه خواهد شد، فرمولی که شما نوشتید درسته و پیچیدگی آن برابر n است. اما مسئله ما این نیست. تعداد فراخوانی ها ملاکی برای پیچیدگی توابع بازگشتی بکار میرود و ضریب آن فقط در جواب مسئله تاثیر دارد.
فرضی که شما کردید برای مسئله ای مانند پیمایش پیش ترتیب یک درخت باینری است.
در کل شما برای حل مسئله بالا باید رابطه زیر را حل کنید.


T(n)=T(n/2)+k

موفق باشید

[mehdad.koulab]

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

[RF.Ariyapoor]

همونطور که withehat عزیز گفت به نظر من هم اردر این تابع log n هست البته چیزیکه باید ذکر بشه اینه که مبنای لگاریتم 2 هست

[delfi01]

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

چيزايي كه بايد بدونيم:

اگر تعدادي دستور ثابت داشته باشيم زمان اجراي آن ثابت مي شود.
اگر k قسمت با زمان اجراي متفاوت داشته باشيم زمان اجراي كل جمع آن زمان اجرا ها مي شود.
اگر حلقه داشته باشيم زمان اجراي حلقه را بدست مي آوريم در تعداد تكرار آن ضرب مي كنيم زمان اجراي كل بدست مي آيد.

موقعي كه مثلا n مرتبا به يه چيزي تقسيم ميشه مثلا نصف ميشه log n بار در مبناي 2طول مي كشه يا اگر مثلا 3/4 بشه log n بار اينبار در مبناي 4/3 ميشه
در مورد تابع هاي بازگشتي من اول سعي مي كنم فرمول تابع زماني رو بدست بيارم بعد اگه شد با قضيه اصلي پيچيدگي رو حدس بزنم اگه نشد با توجه به شكل فرمول يه حدس مي زنم بعد اثبات با حدس و استقرا يا درخت جايگشت يا تكرار با جايگذاري


همونطور که withehat عزیز گفت به نظر من هم اردر این تابع log n هست البته چیزیکه باید ذکر بشه اینه که مبنای لگاریتم 2 هست
در مورد مبنا ،مبنا خيلي براي ما مهم نيست تاكيد مي كنم معمولا براي ما مهم نيست.


:لبخندساده:اگه توضيح بيشتري ميخواين در خدمتتون هستم.

[atilla snowman]

من هم معتقدم که تابع زمان اجرای این الگوریتم عضو ( O (n هستش.
روش کلی همون طور که دوستمون گفتن به دست آوردن تابع صریح یا بازگشتی(و تبدیل اون به صریح) و سپس به دست آوردن تابع مجانبی مناسب هستش که تو اعداد بالا میتونه معیار کارآیی مناسبی باشه.
روشهای مختلفی واسه به دست آوردن تابع صریح وجود داره. حالت سادش با همون توضیحات قبلی پیدا میشه. ولی وقتی بخای به صورت سرشکن شده حساب کنی کار کمی مشکل میشه.میتونی از کتاب CLRS بخش Amortized Analysis کمک بگیری.
تبدیل رابطه ی بازگشتی تو این الگوریتم خیلی سادست. بعضی وقتها به قدری سخت میشه که حتی master theorem هم جواب نمیده. اینجاست که پای تجربه میاد وسط و باید حدس زد و اثبات کرد. معمولا به استقرا اثبات میشن.

[manager]

پیچیدگی این تابع با استفاده از روش اصلی برابر است با : ɵ(logn)
با استفاده از روش جایگذاری نیز ثابت می شود تابع پیچیدگی محاسباتی این الگوریتم عضو O(logn) است.
همونطور که آقای whitehat به اون اشاره کردند تابع بازگشتی صحیح عبارت است از :

T(n)=T(n/2)+1

که البته منظور از 1 انتهایی پیچیدگی زمانی مورد نیاز برای ترکیب پاسخ به دست آمده از اجرای n-1 جهت محاسبه پاسخ nام است و نه 1 انتهایی در عبارت

test:=2*test(n/2)+1

[dadvand]

من هم با اطمینان 99.999% معتقدم پیچیدگی آن برابر logn است .
شما آن الگوریتم را با این الگوریتم اشتباه گرفته اید


Function Test(n:integer):Integer;
Begin
if n=1 then test:=1;
Else Test:=Test(n/2)+Test(n/2)+1
End;

در صورتی که این دو از لحاظ پیچیدگی باهم کاملا فرق دارند .
پیچیدگی این الگوریتم

O(2^logn)=O(n) است ولی پیچیدگی الگوریتم آن الگوریتم O(logn) است .
هر دوی این الگوریتم یک جواب را تولید خواهند کرد ولی پیچیدگی های آنها کاملا متفاوت است .
در این الگوریتم در هر بار فراخوانی ، تابع در بازگشتی دو بار فراخوانی میشود ولی در آن یکی یک بار ولی حاصل آن ضریب دو میشود یعنی بجای دو بار فراخوانی مشابه یک تابع ، یک بار فراخوانی صورت میگیرد و در 2 ضرب میشود .
صحبتهای دوستان هم مکمل این بحث است .
موفق باشید .

[m.abbasi.kia]

سلام به همه این تابع از مرتبه (O(n است با استفاده از قضیه اصلی به راحتی میشه گفت و البته میشه واسه حل به علاوه قضیه اصلی از تغییر متغییر 2 به توان K استفاده کرد که دست آخر بازم همون o(n) رو میده

[m.abbasi.kia]

با سلام خدمت همه . من حرفم رو پس میگیرم. این تابع پیچیدگی log n در مبنای 2 داره . دلیلش هم
تو بحث پیچیدگی زمانی مدت زمانی که عمل اصلی انجام میشه مد نظره که اینجا جمع با عدد یک هستش و خود تابع هم یک بار با پارامتر نصف یعنی n/2 فراخوانی میشه پس تابه هزینه واسه پیچیدگی زمانیt(n)=t(n/2)+1 هستش که حالا با هر روشی که شما بگین اثبات میشه که O(log n) هست مرتبش.

[Developer Programmer]

من حرفم رو پس میگیرمحل پیچیدگی های توابع بازگشتی، نسبتا دشواره اما روش حل اونها بطور جامع در انتهای کتاب طراحی الگوریتهای ترجمه جعفر نژاد توضیح داده شده.