زمان کنونی: ۱۷ آذر ۱۴۰۳, ۰۸:۳۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

طراحی الگوریتم

ارسال:
  

*angle* پرسیده:

طراحی الگوریتم

با سلام
جواب این سوال چی میشه
[tex]if f= O(g) then 2^{f} \epsilon O (2^{g})[/tex]
tex]

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

۰
ارسال:
  

azad_ahmadi پاسخ داده:

طراحی الگوریتم

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

۰
ارسال:
  

mfXpert پاسخ داده:

طراحی الگوریتم

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

ارسال:
  

azad_ahmadi پاسخ داده:

RE: طراحی الگوریتم

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

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

۰
ارسال:
  

ahp89 پاسخ داده:

RE: طراحی الگوریتم

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

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

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

۰
ارسال:
  

azad_ahmadi پاسخ داده:

طراحی الگوریتم

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

ارسال:
  

ahp89 پاسخ داده:

RE: طراحی الگوریتم

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

مگه نباید بعد از علامت عضویت یکی از علامت های تتا و یا امگا و یا اُ بیاد؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

azad_ahmadi پاسخ داده:

طراحی الگوریتم

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

ارسال:
  

ahp89 پاسخ داده:

RE: طراحی الگوریتم

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

یعنی شما میگید این اشتباهه؟
[tex]if n=o(n^{2}) then 2^{n}\epsilon o(2^{n^{2}})[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۰
  

azad_ahmadi پاسخ داده:

طراحی الگوریتم

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

۰
ارسال: #۱۱
  

m_sardaari پاسخ داده:

طراحی الگوریتم

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

۰
ارسال: #۱۲
  

*angle* پاسخ داده:

طراحی الگوریتم

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

ارسال: #۱۳
  

azad_ahmadi پاسخ داده:

RE: طراحی الگوریتم

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

سلام. بله جواب سوال اشتباه است. موفق باشی.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۴
  

roofia پاسخ داده:

طراحی الگوریتم

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

کـــــــــــــــــــــــــــمکــــــــــــــــــــــــــــــــــــــــــــــــــ​ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ!​!!!!!!!!!!!!!!!!!!!!!!!
نقل قول این ارسال در یک پاسخ

ارسال: #۱۵
  

azad_ahmadi پاسخ داده:

RE: طراحی الگوریتم

(۲۹ مهر ۱۳۹۱ ۰۴:۱۶ ب.ظ)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 خواهد بود.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۶
  

roofia پاسخ داده:

طراحی الگوریتم

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

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

ارسال: #۱۷
  

azad_ahmadi پاسخ داده:

RE: طراحی الگوریتم

(۲۹ مهر ۱۳۹۱ ۰۷:۳۶ ب.ظ)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 پاسخ داده:

طراحی الگوریتم

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

۰
ارسال: #۱۹
  

razaghian پاسخ داده:

طراحی الگوریتم

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

راهنمائـــــــــــــــــــــــــــــــــــــــــــــــــــــیم کنید خواهشا!!!!!
نقل قول این ارسال در یک پاسخ

ارسال: #۲۰
  

naderx پاسخ داده:

RE: طراحی الگوریتم

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

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

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

۰
ارسال: #۲۱
  

razaghian پاسخ داده:

طراحی الگوریتم

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

بله سی پلاس پلاس:-)
نقل قول این ارسال در یک پاسخ

ارسال: #۲۲
  

naderx پاسخ داده:

RE: طراحی الگوریتم

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

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

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

۰
ارسال: #۲۳
  

razaghian پاسخ داده:

طراحی الگوریتم

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

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

("افسانه دونگی") هم فیلم جالبیه:-)
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  طراحی یک سیستم نورانی هوشمند marvelous ۹ ۶,۳۶۰ ۱۳ آذر ۱۴۰۳ ۰۵:۱۰ ب.ظ
آخرین ارسال: آموزش طراحی سایت در تبریز
  [دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی هاتف ۳۳ ۴۴,۶۶۷ ۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ
آخرین ارسال: solmaz58
  طراحی ui/ux kimiya1234 ۲ ۲,۴۳۳ ۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ
آخرین ارسال: farsamw
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۳۷ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  طراحی یک سیستم عامل (از صفر) sina4everafter ۱۲ ۱۶,۷۷۴ ۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ
آخرین ارسال: nahalmomen2007@yahoo.com
  طراحی سایت ریسپانسیو wikidemy1 ۰ ۱,۸۷۹ ۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ
آخرین ارسال: wikidemy1
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۷۴۸ ۳۰ آذر ۱۳۹۹ ۰۸:۲۴ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  طراحی الگوریتم ها amir.m5560@gmail.com ۰ ۱,۵۸۱ ۳۰ آذر ۱۳۹۹ ۰۸:۲۰ ب.ظ
آخرین ارسال: amir.m5560@gmail.com
  مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲) Farid_Feyzi ۵ ۷,۸۴۷ ۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ
آخرین ارسال: s-taheri
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۳,۶۷۹ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close