نحوه‌ی محاسبه‌ی پیچیدگی زمانی

[DumanNazeri]

با سلام خدمت اساتید بزرگوار٬
من نمی‌دونم که قسمت درستی از انجمن رو برای پرسیدن سوالم انتخاب کردم یا نه.. پیشاپیش از محضرتون عذر می‌خوام.
سوالی که دارم در مورد درس ساختمان داده‌ها است و مربوط به بخش محاسبه‌‌ی پیچیدگی زمانی الگوریتم‌ها هست..
متاسفانه استاد ما این بخش رو خیلی بد و بدون توضیح درس دادن! هیچ کس متوجه نشد!
مدیون عزیزانی می‌شم که بنده رو راهنمایی می‌فرمایند. [در مبتدی‌ترین حالت ممکن!]


for i = 1 to n do
for j = 1 to i do
a++;


برای مثال پیچیدگی این الگوریتم چطور محاسبه می‌شه؟

[DumanNazeri]

اساتید محترم اگر کتابی رو می‌شناسن که این گونه مسائل رو خوب و کامل توضیح داده باشه و خوندنش برای من مبتدی رو مفید تشخیص می‌دن٬ لطفن معرفی بفرمایند.

[alisafaie]

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

ایجا یک نمونه کتاب در این مورد قرار داده شده. مطالعه کنید. سوالی داشتید در انجمن بپرسید


http://dlbook.net/?p=11118

[ali_md110]

سلام
یک تاپیک جواب دادم اگر خوب متوجه نشدید پیام بدید راهنمایی میکنم
http://barnamenevis.org/showthread.php?405543

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

حلقه for یک بدنه داره و یک دستور


for(i=1;i<=10;i++) دستور حلقه
2*i بدنه حلقه


مثال شما


for i = 1 to n do

for j = 1 to i do

a++;






برای محاسه از فرمول زیر استفاده میکنیم
برای محاسبه پیچیدگی دستور حلقه: 1+(1+حدپایین-حد بالا)
حالا منظور از حد بالا و پایین چیه؟
منظور از حد پایین :مقدار شروع حلقه یعنی i=1 و یعنی عدد 1 هست
پس حد پایین مساوی 1

منظور از حد بالا میشه عددی که در شرط دستور حلقه i to n قرار داده شده یعنی n هست

پس حد بالا هم شد n

حالا اگر در فرمول جایگذاری کنیم پیچیدگی بدست میاد 1+ ( 1+ 1 - n)
حاصل :اگر عدد 1- و 1+ درون پرانتر را با هم ساده کنیم فقط n میمونه پس جواب دستور حلقه با براکت دورش خط میکشم
[(n)+1]
اگر دقت کنیم در حلقه ها جواب درون پرانتر در بدنه حلقه ضرب میشه منظورن (n) هست که باید در بدنه ضرب بشه
چون این خلقه تو درتو هست عدد طبق قرمول پیچیدگی دستور for دوم هم بدست میاریم1+(1+حدپایین-حد بالا)
حد بالا میشه i
حد پایین میشه j=1 و در نهایت عدد 1
جاصل دستور حلقه دوم: 1+(i-1+1) و جواب ساده شده=
(i)+1
گفتیم که حاصل حلقه ها در بدنه تاثیر گذار هست پس nپرانتر حلقه اولی رو هم در جواب حلقه دوم ضرب میکنیم

[(i+1)*n]

میمونه بدنه حلقه که a++ هست و در طراحی الگوریتم به عبارت ++ امتیاز 1 داده میشود
برای بدست آوردن پیچیدگی بدنه حلقه:
حالا کاری که باید بکنیم بیایم جوابهای درون پرانتر هر دو دستور حلقه (n)و (i) که بدست آوردیم در جواب بدنه حلقه ( a++) یعنی عدد 1 بدست آمده ضرب کنیم
حاصل جواب بدنه حلقه میشه

[1*n*i]


تا اینجا جوابهای دوتا حلقه for و بدنه بدست اوردیم و هر کدومشون گذاشتیم داخل براکت مشخص کردم

در نهایت باید این جوابها را با هم جمع بکنبم

T(n)=(n+1)+(i+1*n)+(1*n*i)

[alirzafrzn]

سلام لطفا کسی میتونه این رو محاسبه کنه و روش محاسبه زمانی رو برام بنویسه خیلی خیلی ممنونش میشم
147837استادش گفته از لگاریتم و سیگما داخل هم لازمه استفاده بشه برای زمان اجرای الگوریتم بلد نیستم