mahdiii

پس سوال یک و دو مشخصه. دو همون !n میشه فکر کنم. لطفا چهار رو روش بحث کنین. چطور گفتین میشه دو. سه هم یکم مشکوکه. اگه منظورش درخت کامل بود میشد دو اما در این صورت فکر کنم جواب همه غلطه. همون طوری که گفتن. چون برای مثلا n=9 بیشتر از 8 از دو میشه درخت دودویی متوازن با اون شرط ارتفاع درست کرد. بقیه گزینه ها هم راحت حذف میشن و پنج هم مشخصه که چهار میشه چون زمانی بیشترین تعداد گره را خواهد داشت که درخت کامل و پر باشه و زمانی کمترین تعداد گره را خواهد داشت که در هر سطح تنها دو گره داشته باشیم پس میشه 2*h و یکی هم خود ریشه میشه 2h+1. فقط رو چهار اگه کسی میدونه بحث کنه.

mahdiii

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

mahdiii

6-4
7-3
8-1

mehran2008

مرسی آقا مهدی.

پس اگه موافق باشید، به عنوان اولین مرحله کار، سوالات 4، 10، 11 و 18 رو که مربوط به هزینه های محاسباتی هستند، بررسی کنیم. من سعی می کنم جواب تشریحی این سوالات رو تا جایی که بلدم، تا یکی دو روز آینده اینجا قرار بدم. البته اگه سایت باز بشه برام.

mardin200

دوستان خسته نباشيد. كارتون عاليه
به نظر من به ترتيب سوال جلو بريم بهتر خواهد بود چون بعدا افردي كه بخوان استفاده كنن براشون راحتتره

در مورد سوال 4 عناصر ماتريس توليد شده 1 يا 1- خواهند بود پس هيچ حاصلضربي وجود نخواهد داشت فقط بايد حاصلجمع ها را شمرد . ساده ترين روش كه از مرتبه n^2 خواهد بود. اگر هم تمام عناصر V برابر باشند كه فقط اولين عنصر ماتريس حاصل مقدار دارد بقيه عناصر صفر خواهند شد. يعني الگوريتم از مرتبه n خواهد بود
ولي در سوال عناصر V برابر نيستند. براي ماتريس A تمام عناصر سطر اول 1 خواهد شد و براي بقيه سطرها نصف عناصر 1 و نصف ديگر 1- خواهند بود . من يك الگوريتم با n*n/2 تونستم براش تعريف كنم ولي هرچي زور زدم نتونستم nLog n پيدا كنم.
ولي با توجه به گزينه ها به نظر ميرسه همون nLog n باشه

__________________

mehran2008

سلام،

جواب سوال 4 رو من خودم مشکل دارم. اگر کسی از دوستان بتونند توضیح بدند، ممنون میشم.
جواب سوال 10، گزینه 2 هست. نکته های این سوال اینه که * lg برای اعداد بسیار بزرگ کمتر از 7 است. پس کم هزینه ترین مورد است. g6 هم از g5 کم هزینه تره. مثلا اگر n رو برابر 2 به توان 32 فرض کنیم، متوجه می شیم.
جواب سوال 11 گزینه 3 است. چون سایز ورودی 10 برابر شده و زمان اجرا 100 برابر.
جواب سوال 18 هم گزینه 3 است. چون بیت k ام 2 بار، بیت k-1 ام، 4 بار و ... بیت اول 2 به توان k (یا همان n بار) تغییر مقدار می دهد.

mahdiii

من با جوابهای شما موافقم. فقط چجوری اون log*ثابت میشه از همه کمتره. log*n^n
بعدش بریم سراغ سوالای درخت؟ لطفا مشخص کنید

mardin200

من اون چيزي كه بلد بودم در مورد سوال 4 گفتم و در مورد سوال 10 و 11 با شما موافقم.
ولي سوال 18 كمي نامفهومه. خب اگه تعداد تغييرات بيتها مورد نظرش هست كه اولين بيت سمت راست 2 به توان k منهاي 1 بار تغير ميكند و هر بيت كه به سمت چپ بياييم تقسيم بر 2 مي شود چنانكه با ارزشترين بيت فقط يك بار تغيير مي كند.
حاصلجمع همه اينها برابر 2 به توان k+1 منهاي k منهاي 2 خواهد بود كه با هيچ گزينه اي هم خواني ندارد حال اگر تقسيم بر 2 به توان k هم شود باز گزينه مناسب براش وجود ندارد
جالب اينجاست كه چرا حد بالاي سيگما را برابر n قرار داده بايد برابر k مي بود در مورد گزينه 2 و 4 هم چيزي به نظرم نمي رسد

__________________

mahdiii

آره. سوالش یکم مشکل داشت. باید اون k باشه نه n. اما اگه شما اونو n بگیری جملات بعد از k ت کسری میشه که می تونی صفر اونو درنظر بگیری. در ضمن مرتبش میشه o(2^n)
سوالای درختو حل کنیم. من می خوام سریعتر به سوالات یادگیری برسیم.

mardin200

يعني به نظر شما گزينه 2 درسته؟ استدلالتون چيه كه ميگيد از مرتبه n^2 است؟ آخه سوال اصلا مرتبه پيچيدگي نخواسته!!!!
در ضمن منم ميگم سريعتر بريم جلو
دوستمون كه قرار بود دسته بندي كنه سريعتر بزاره در غير اينصورت همون ترتيب سوالاتو بريم جلو

__________________