انجمنصفحه اولجستجوی انجمن

[ka arman]

(۲۴ بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

سلام...
به نظر من میشه (O(n+lgn)=O(n

[mehdi1902]

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

(24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

من زدم n
مشکل کار اینجاست که سوال مشخص نکرده ما گره رو داریم یا نه
چون گفته بود گرهی من فرض کردم که نداریم و با یک dfs میشه از پیچیدگی n
اگر هم منظور دونستن گره بوده میشه log n

منم n زدم. احتمالن منظورش این بوده که گره معلوم نیس

[راضیه اکبری]

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

(24 بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط:  برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

اگر هر دو آرایه باشن میشه به صورت درجا با O(N) هیپ ساخت.

درسته ولی قبلش برای تولید ارایه هزینه mlogm+nlogn داریم دیگه نداریم ؟ یعنی جواب nlogn+mlogm نیست؟

[izadan11]

یه سوال دیگه بود گفته بود یک ستاره داریم که
من زدم نود دیگری وجود دارد که ستاره باشد برای رد بقیه ی یک شکل کشیدم بقیه ی گزینه ها رد شدن(شکل رو بعد کنکور هوش می ذارن الان توانش رو ندارم)
یه سوال دیگه هم بود مربوط به پوشا من زدم وزن های متمایز(سوال دقیقش یادم نیست)

[Fot30]

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

(24 بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط:  برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

این سوالش اشتباه نبود :-؟
یه دونه O(n) برای تبدیل مین به ماکس. یه دونه min {logn , log m} هم برای اینکه به هم وصل بشن. مثلن ماکس یکی رو بیاریم ریشه و مرتبش کنیم درخت رو و فرزند دیگه شو بذاریم اون یه درخت. یعنی میشه
n + min {logn , logm}

شما وقتی دو تا آرایه رو به هم تو یه آرایه ادغام میکنید زمان m+n-1 نیازه فکر کنم
در نهایت شما یک آرایه m+n+1 عنصری نامرتب خواهید داشت که با مرتبه زمانی O(m+n) هیپ را با آرایه به صورت درجا خواهید ساخت. اصلا نیاز به logm یا logn و این چیزا نیستش بنظرم

[AMTP]

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

[blue70]

ممنون...
بعد اینو هم میشه بگین
اون سوالی که گفته بود چند مورد درست می باشد ...و گزینه ها pudh و pop داشتند و (۱)o .... چند گزینه درست بود ؟ من خودم زدم صفر گزینه چون ساختمان داده ای نداریم که هم درج و هم حذف ازش بشه (۱)o ..داریم ؟

[sahar_rostami2]

گزینه هاش اینا بود:

(N+M)

(NLOGM+MLOGN) من اینو زدم !

(NLON+MLOGM
MIN(....یادم نیس!( Big Grin

[izadan11]

(۲۴ بهمن ۱۳۹۲ ۰۳:۰۱ ب.ظ)blue70 نوشته شده توسط:  ممنون...
بعد اینو هم میشه بگین
اون سوالی که گفته بود چند مورد درست می باشد ...و گزینه ها pudh و pop داشتند و (۱)o .... چند گزینه درست بود ؟ من خودم زدم صفر گزینه چون ساختمان داده ای نداریم که هم درج و هم حذف ازش بشه (۱)o ..داریم ؟

منم زدم صفر ولی مطمئن نیستم نظر طراح کنکور همین باشه

[راضیه اکبری]

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

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

(24 بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط:  برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

این سوالش اشتباه نبود :-؟
یه دونه O(n) برای تبدیل مین به ماکس. یه دونه min {logn , log m} هم برای اینکه به هم وصل بشن. مثلن ماکس یکی رو بیاریم ریشه و مرتبش کنیم درخت رو و فرزند دیگه شو بذاریم اون یه درخت. یعنی میشه
n + min {logn , logm}

شما وقتی دو تا آرایه رو به هم تو یه آرایه ادغام میکنید زمان m+n-1 نیازه فکر کنم
در نهایت شما یک آرایه m+n+1 عنصری نامرتب خواهید داشت که با مرتبه زمانی O(m+n) هیپ را با آرایه به صورت درجا خواهید ساخت. اصلا نیاز به logm یا logn و این چیزا نیستش بنظرم

اخه اولش دو تا هیپ داریم برای اینکه ارایه بشن یه هزینه ای باید بکنیم دیگه , هوممم نمیدونم دیگه

[mehdi1902]

(۲۴ بهمن ۱۳۹۲ ۰۲:۵۹ ب.ظ)izadan11 نوشته شده توسط:  یه سوال دیگه بود گفته بود یک ستاره داریم که
من زدم نود دیگری وجود دارد که ستاره باشد برای رد بقیه ی یک شکل کشیدم بقیه ی گزینه ها رد شدن(شکل رو بعد کنکور هوش می ذارن الان توانش رو ندارم)
یه سوال دیگه هم بود مربوط به پوشا من زدم وزن های متمایز(سوال دقیقش یادم نیست)

اون وزن های متمایز رو فک کنم اشتباه زدی. گزینه ۱ میشد. که گفته بود درخت است :دی
اگه ۳ تا یال باشه که وزن همه ۵ باشه مثلن. درخت پوشا یکی میشه

[hosseinriasati]

سلام به همه
من ساخت هیپ از MinHeap و MaxHeap رو زدم مرتبه n چون کلا ساخت Heap از روی هر ترتیب ورودی با مرتبه n انجام میشه البته این نظر منه.
T(n,k هم زدم مرتبه nk چون شبیه کنکور کامپیوتر پارسال بود که اونم جوابش میشد nk
نویز هم مگه روی AVL اتفاق میفته؟ جل الخالق. اینم زدم مرتبه n چون فکر کردم اگر inorder پیمایش بشه باید ترتیب صعودی حفظ بشه که در صورت اتفاق افتادن نویز ترتیب صعودی از بین میره.
در مورد مرتب سازی مقایسه ای فکر کنم هر دو جمله اشتباه بود.

اگر کسی سوالا رو یادشه لطف کنه بنویسه تا برای فردا بفهمیم چی رو اشتباه کردیم. با تشکر

[sahar_rostami2]

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

(24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

من زدم n
مشکل کار اینجاست که سوال مشخص نکرده ما گره رو داریم یا نه
چون گفته بود گرهی من فرض کردم که نداریم و با یک dfs میشه از پیچیدگی n
اگر هم منظور دونستن گره بوده میشه log n

منم n زدم

[virtual girl]

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

(24 بهمن ۱۳۹۲ ۰۲:۵۴ ب.ظ)izadan11 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

من زدم n
مشکل کار اینجاست که سوال مشخص نکرده ما گره رو داریم یا نه
چون گفته بود گرهی من فرض کردم که نداریم و با یک dfs میشه از پیچیدگی n
اگر هم منظور دونستن گره بوده میشه log n

منم n زدم. احتمالن منظورش این بوده که گره معلوم نیس

من زدم logn توجه داشته باشید گفته بود " تشخیص درخت" ! این کلمه تشخیص گفته منظورش چیه دیگه !

[mehdi1902]

(۲۴ بهمن ۱۳۹۲ ۰۳:۰۰ ب.ظ)AMTP نوشته شده توسط:  یکی از سوالا گفته بود چند جمله صحیح است جملاتشم نزدیک بودن: ساختمان داده ای با قابلیت پوش و پاپ و یافتن مین و ماکس از مرتبه ۱
فک کنم دو جملش صحیح بود درسته؟

من اینو ۰ زدم :دی
گند زدم یعنی ؟ :-؟
نمیشه که هم درج هم عنصر مین از مرتبه O(1) باشه که. میشه آیا ؟‌:-؟