PDA

View Full Version : مر تبه و زمان اجرا



armiya
یک شنبه 25 مهر 1389, 23:28 عصر
با سلام
این مطلب رو کسی میتونه اثبات کنه عدد 8 معادل نماد تتا می باشد

http://www.ecapic.ir/image2/ECA-101017235104.jpg
http://www.ecapic.ir/image2/ECA-101017235104.jpg

f(n)+Of(n)=8f(n)
که 8 نماد تتا میباشد

armiya
جمعه 30 مهر 1389, 23:26 عصر
ایا این مرتبه درسته اگه هست چطور اثبات میشه؟

مسعود اقدسی فام
شنبه 01 آبان 1389, 00:05 صبح
ایا این مرتبه درسته اگه هست چطور اثبات میشه؟


O و تتا مجموعه توابع هستن و f یه تابع. چطور می شه اینها رو با هم جمع زد؟ یا منظور اضافه کردن تابع f به مجموعه توابع O هست اینجا؟




{f(n)}+O(f(n)) = 8(f(n))



اینطوریه؟

armiya
شنبه 01 آبان 1389, 00:33 صبح
بله منظور همونه که شما نوشتید البته یه چند تا دیگه هم هستش

مسعود اقدسی فام
شنبه 01 آبان 1389, 19:37 عصر
خب، عمل جمع همون مفهوم اجتماع رو داره. یعنی A + B = A U B.

یعنی قصد داریم دو مجموعه رو با هم ادغام کنیم.

حالا سوال من اینه که آیا یه تابع عضو مجموعه‌ی اوی بزرگ خودش نیست؟

یعنی ( f( n عضو ( ( O ( f ( n نیست؟

اگه اینطور باشه - که هست - جمع اون با اوی بزرگ، خود اوی بزرگ می‌شه.

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

سوال پرسیده آیا صحیح است؟ یا گفته ثابت کنید؟

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

armiya
یک شنبه 02 آبان 1389, 00:10 صبح
نه گفته این رو ثابت کنید که درسته.
همین

مسعود اقدسی فام
یک شنبه 02 آبان 1389, 00:30 صبح
نه گفته این رو ثابت کنید که درسته.
همین

تمرین کتابه؟

armiya
یک شنبه 02 آبان 1389, 00:40 صبح
بله طراحی الگوریتم هادی یوسفی

مسعود اقدسی فام
یک شنبه 02 آبان 1389, 19:49 عصر
بله طراحی الگوریتم هادی یوسفی

توضیحاتی که من اینجا دادم اشتباهی داشت به نظر شما؟ اگه کسی تونست براتون همینطوری که هست اثبات کنه بی خبرم نذارید. دوست دارم بدونم اشکال کارم کجاست اگه واقعا اشتباه استدلال کردم.