اشتباهه. چون مثلا f = 2n و g=n ، هرچند هردو از مرتبه Oبزرگ n هستند اما بعد از then این شرط برقرار نیست و f از g بزرگتر میشه.

(۱۱ مهر ۱۳۹۱ ۱۱:۴۸ ب.ظ)azad_ahmadi نوشته شده توسط:  اشتباهه. چون مثلا f = 2n و g=n ، هرچند هردو از مرتبه Oبزرگ n هستند اما بعد از then این شرط برقرار نیست و f از g بزرگتر میشه.

توابع f و g که مثال زدید مناسب نیستند چون ۲n از مرتبه لیتل اُوی n نیست

(۱۲ مهر ۱۳۹۱ ۰۲:۱۹ ب.ظ)mfXpert نوشته شده توسط:  

(11 مهر ۱۳۹۱ ۱۱:۴۸ ب.ظ)azad_ahmadi نوشته شده توسط:  اشتباهه. چون مثلا f = 2n و g=n ، هرچند هردو از مرتبه Oبزرگ n هستند اما بعد از then این شرط برقرار نیست و f از g بزرگتر میشه.

توابع f و g که مثال زدید مناسب نیستند چون ۲n از مرتبه لیتل اُوی n نیست

سلام. قبل اینکه جواب رو بنویسم، نوشته بودم "آیا اون o، اوی بزرگه یا اوی کوچیک؟" اما پاکش کردم و حدسمو گذاشتم بر اینکه اوی بزرگ باشه. شما درست می گین. ممنون.
---------------------------------------
درضمن اون عکس پروفایلت رو من تا چند ماه فکر می کردم عکس خروسه اما امروز متوجه شدم که خروس نیست
موفق باشی .

(۱۰ مهر ۱۳۹۱ ۰۲:۳۵ ب.ظ)*angle* نوشته شده توسط:  با سلام
جواب این سوال چی میشه
[tex]if f= o(g) then 2^{f} \epsilon (2^{g})[/tex]

ایا درست هست نتیجه یا نه و چرا
ممنون میشم پاسخ بدید
با سپاس

احساس میکنمو احتمالا سوال مشکل داره که احتمالا مشکل تایپیه!!!
بعد از then رو دقت کنین,و احتمالا بعد از علامت عضو رو دقت بفرمایین.
اگه من اشتبا میکنم لطفا بگین.

سوال مشکل نداره و کاملا درسته.
جوابش هم میشه "اشتباه است".

(۱۲ مهر ۱۳۹۱ ۱۱:۲۲ ب.ظ)azad_ahmadi نوشته شده توسط:  سوال مشکل نداره و کاملا درسته.
جوابش هم میشه "اشتباه است".

مگه نباید بعد از علامت عضویت یکی از علامت های تتا و یا امگا و یا اُ بیاد؟

اشتباه تایپی رو باید حدس زد
قبلش نوشته اگه f عضو اوی کوچیک g باشه، پس احتمالا منظورش بعد از then همون اوی کوچیک هست.
اشتباه تایپی به وفور یافت میشه دوست عزیز.

(۱۲ مهر ۱۳۹۱ ۱۱:۲۹ ب.ظ)azad_ahmadi نوشته شده توسط:  اشتباه تایپی رو باید حدس زد
قبلش نوشته اگه f عضو اوی کوچیک g باشه، پس احتمالا منظورش بعد از then همون اوی کوچیک هست.
اشتباه تایپی به وفور یافت میشه دوست عزیز. نگران نباش. موفق باش.

یعنی شما میگید این اشتباهه؟
[tex]if n=o(n^{2}) then 2^{n}\epsilon o(2^{n^{2}})[/tex]

ببینید من تو پست شماره ۲، فرض رو بر این گذاشتم که اون او، اوی بزرگ هست. اگه اینطور باشه که جواب اشتباهه و مثال هم زدم. اما اگه اوی کوچیک باشه، درست خواهد بود.

به نظز من اگه هر دو o کوچک باشند رابطه درسته چون در قسمت اول ثابت میشه که درجه f از G کمتره یعنی حالاتی که میشه مثال زد برای این دو مثل: f=n ,g=n^2 و در قسمت دومم با توجه به این مثال درسته

مرسی از پاسخ من بد تایپ کردم عذرخواهی می کنم منظورم ا بزرگ بود که در اینصورت طبق نظر شما این رابطه اشتباه می شوذ؟

(۱۶ مهر ۱۳۹۱ ۰۱:۳۳ ق.ظ)*angle* نوشته شده توسط:  مرسی از پاسخ من بد تایپ کردم عذرخواهی می کنم منظورم ا بزرگ بود که در اینصورت طبق نظر شما این رابطه اشتباه می شوذ؟

سلام. بله جواب سوال اشتباه است. موفق باشی.

این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)

---

کـــــــــــــــــــــــــــمکــــــــــــــــــــــــــــــــــــــــــــــــــ​ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ!​!!!!!!!!!!!!!!!!!!!!!!!

(۲۹ مهر ۱۳۹۱ ۰۴:۱۶ ب.ظ)roofia نوشته شده توسط:  این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)

---

کـــــــــــــــــــــــــــمکــــــــــــــــــــــــــــــــــــــــــــــــــ​ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ!​!!!!!!!!!!!!!!!!!!!!!!!

مرتب سازی ادغامی هر بار مجموعه داده شده رو تقریبا نصف می کنه، تا بجایی برسه که ادامه نصف کردن امکان پذیر نباشه.
پس چون هر بار مجموعه نصف میشه، به دو مجموعه تقسیم بندی میشه. (یعنی n ، به دو مجموعه n/2 تبدیل میشه).
پس تا اینجا ۲T(n/2 مشخص شد. اون n-1 که نوشتین زمان لازم برای مقایسه عناصر بوده که از مرتبه تتای n است.
حالا رابطه بازگشتی که شما نوشتین رو میشه راحت با قضیه اصلی بدست آورد. که جواب برابر تتای nlogn خواهد بود.

خب ببخشید چطوری با جاگذاریn=2^k میشه به تتای nlog رسید؟
کلا من میخوام بدونم چطوری و با چه محاسباتی میشه به تتای nlogn رسید؟

---

خب چه محاسباتی روی اون معدله باید انجام بدم تا برسم به تتایnlogn ؟

(۲۹ مهر ۱۳۹۱ ۰۷:۳۶ ب.ظ)roofia نوشته شده توسط:  خب ببخشید چطوری با جاگذاریn=2^k میشه به تتای nlog رسید؟
کلا من میخوام بدونم چطوری و با چه محاسباتی میشه به تتای nlogn رسید؟

---

خب چه محاسباتی روی اون معدله باید انجام بدم تا برسم به تتایnlogn ؟

ببینید، اون n=2^k رو برای راحتی کار فرض کرده، یعنی فرض کرده که طول آرایه ای که می خواد ادغام کنه طوری باشه که دقیقا نصف بشه. پس اگه اون n=2^k رو هم تو مفروضات نباشه مهم نیست.
قضیه اصلی یا master برای همچین حالاتی میتونه جواب رو بدست بیاره. شما یک بار اون قسمت رو بخون، حتما متوجه میشی.
چون ۲ به توان (لگاریتم a در مبنای b) برابر با n میشه، که a همون ۲ قبل از Tn و b همون ۲ که در مخرج وجود داره (n/2) هست، و مقدار زمان برای ادغام و مقایسه برابر با تتای n بوده، پس این Tn با این زمان ادغام و مقایسه برابر بوده و در صورت برابری این دوتا جواب میشه تتای nlogn . ( اذعان می کنم خیلی بد توضیح دادم، بهت حق میدم متوجه نشی، شما قضیه اصلی رو بخون متوجه خواهی شد)
موفق باشی.

راه حل تشریحی فرمول روابط بازگشتی مرتب سازی ادغامی رو میخوام!

در مرتب سازی ادغامی دوتا لیست دارن با هم ادغام میشن و مرتب میشن.این رو کاملا بلدم.
حالا چطوری میتونم همین روال رو برای سه تا لیست تعمیم بدم؟
میشه راهنماییم کنید؟

---

راهنمائـــــــــــــــــــــــــــــــــــــــــــــــــــــیم کنید خواهشا!!!!!

(۰۱ آبان ۱۳۹۱ ۰۸:۱۳ ب.ظ)razaghian نوشته شده توسط:  در مرتب سازی ادغامی دوتا لیست دارن با هم ادغام میشن و مرتب میشن.این رو کاملا بلدم.
حالا چطوری میتونم همین روال رو برای سه تا لیست تعمیم بدم؟
میشه راهنماییم کنید؟

---

راهنمائـــــــــــــــــــــــــــــــــــــــــــــــــــــیم کنید خواهشا!!!!!

سلام
خوب سه تا اشارگر نیاز داری که به اول سه لیست اشاره کنه مثلآ i و j و k بعد باید با دو مقایسه ببینی کدامیک از این شه مقداری که این اشاره گر ها بهش اشاره میکنن کوچکتره ٰ و بعد اونو داخل آرایه نهایی بریزی و الی آخر ...
میخواهی برنامشو بنویسم برات ؟ به زبان سی پلاس پلاس بنویسم ؟

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

---

بله سی پلاس پلاس:-)

(۰۱ آبان ۱۳۹۱ ۰۹:۱۸ ب.ظ)razaghian نوشته شده توسط:  سلام!
الگوریتمشو میخوام.
واسه درس طراحی الگوریتم.
با آرایه!
اگ بنویسید که لطف بزرگی میکنید در حقم!

---

بله سی پلاس پلاس:-)

اولش که برنامه رو شروع کردم به نوشتن ، گفتم آسونه ! بعدش دیدم ناجوره ! البته مشکل خاصی نبود ولی یکم ریزه کاری داشت و تا جایی که تونستم جوری نوشتم که خوانایی برنامه حفظ بشه ولی در کل برنامه روتینی نیست که با یک نگاه بشه ازش سر در آورد. (در ضمن شاید یه بنده خدایه دیگه بهتر از من بنویسه چون من هنگام دیدن برنامه مورد علاقم ("افسانه دونگی") داشتم کد مینوشتم ! زیاد بهینه نیست ولی صد در صد درسته) و اینم بگم که ایدش همون ادغام دو آرایه هست و چیزی نیست که از کره مریخ اومده باشه

خوش به حالتون.چقد بلدید.حالم از خودم به هم خورد.:-(

دستتون درد نکنه.خیلی لطف کردید واقعا!

("افسانه دونگی") هم فیلم جالبیه:-)