صفحه‌ها: ۱ ۲
ممنون میشم کسی جواب این سوالو توضیح بده
خیلی حیاتی و فوریه .ممنون
فکر می کنم جوابش گزینه ۲ بشه!درسته؟!
با استفاده از یه BST که تعداد تکراری ها رو برای هر اندیس میشماره در همین مرتبه درج میکنیم و بعد LDR پیمایش می کنیم.
البته از هش هم فک کنم بشه حلش کرد!
پاسخ ساده هست
ببینید
اگر n عنصر متمایز بود پاسخ میشد nlogn
ولی حالا k دسته داریم که رویهم میشن n تا
خب من میام این k ارایه درست میکنم و به کمک این k ارایه یک درخت میسازم خب حالا این میشه درخت انتخابی و هربار مینیم را با logkارتفاع درخت پیدا میکنم چون n عنصر هست میشه nlogk
۵ دقیقه روش فکر کردم سوال جلبی بود کتابها فقط گفتن جواب میشه nlogk و راه حل نگفتن
(۱۱ بهمن ۱۳۹۱ ۱۲:۳۲ ق.ظ)teacherpc نوشته شده توسط: اگر n عنصر متمایز بود پاسخ میشد nlognمیشه خواهشا یه کم بیشتر توضیح بدین؟
ولی حالا k دسته داریم که رویهم میشن n تا
خب من میام این k ارایه درست میکنم و به کمک این k ارایه یک درخت میسازم خب حالا این میشه درخت انتخابی و هربار مینیم را با logkارتفاع درخت پیدا میکنم چون n عنصر هست میشه nlogk
ساخت درخت جستجوی دودویی از مرتبهn هست.ولی وقتی به جای هر راس درخت از یک آرایه استفاده بشه، اونوقت مرتبه اش n^2نمیشه؟
در واقع سوالم اینه که چه جوری nتا اعداد اولیه رو بذاریم تو درخت به ارتفاعk ؟
پیشاپیش ممنون
ببنینید ساخت درخت جستجوی دودویی میشه nlogn
دربدترین حالت میشه nدو
اما اینجا عناصر n تا هستند که تو k دسته تقسیم میشن مثلن اگه بیست تا عدد باشن ۴ تا ۵ داریم ۴ تا ۶ داریم ۴ تا ۱۲ داریم
۴ت ۹ داریم ۴تا ۱۰ داریم خب حالا n=20 , و k=5هست مثل اینه که بگن تمام بچه های مهدکودک رو تو k تا صف مرتب کن که هم قدها تو یک صف باشن و k نفر با قدهای متمایز باشه!
قرارنیست n تا عدد رو بزاریم تو درخت به ارتفاع k
ما k تا ارایه میزاریم کنارهم هرسری عنصراول هرکدوم با بقیه مقایسه میشه و در ارابه نهایی فرار میگیره
شبیه درخت انتخابی میشه متوجه شدین؟
آره اشتباه کردم.حواسم نبود.
مرسی از توضیحاتتون.
من فقط یه نکته ای که متوجه نمیشم:
اینکه گفتین هر سری عنصر اول k آرایه با بقیه مقایسه میشه.
اخه ارایه اولیه n تایی، نا مرتب هست.
مثلا میشه لطفا برای اعداد زیر الگوریتمو اجرا کنین:
۵,۹,۸,۸,۸,۶,۵,۹,۸,۹,۵,۶,۹,۵,۶,۶
در اینجا n برابر ۱۶ هست و k هم ۴ هست.
خب حالا این ۱۶ تا روبه ۴ ارایه ۴تایی تقسیم میکنیم،درسته؟
اونوقت اگر عنصر اول این چهار آرایه باهم مقایسه بشه و در ارایه نهایی قرار بگیره، ممکنه آرایه نهایی مرتب نباشه.
کلا نمیدونم چرا گیج شدم.
ظرفیت k تا ارایه همه یکسان هست رویهم ظرفیتشون میشه n
عناصر هر کدوم از این k ارایه مرتب نیست یعنی k تا ارایه داریم که تو خودشون هم نامرتب هستند
خب حالا ما با عناصر بالای ارایه های (k تا ارایه رو به شکل پشته تصور کن که از بالای هرکدوم یه عنصر میاد بیرون و یه درخت ساخته میشه با عنصر شماره یکم بالای این k ارایه ) خب بعد از اینکه درخت ساخته شد دیگه کار تمامه هر بار هر ارایه ای که مینیمم بود عنصربالای خودش(به شکل پشته تصور کنیدش برااینکه متوجه شید ولی پشته نیستا حواست باشه!) را میفرسته تو درخت و این عنصر ارتفاع درخت رو طی میکنه(min تزریق میشه تو درخت ) و چون n عنصر داریم هر عنصر مجبوره از ارتفاع درخت طی کنه هر عنصری زودتر رسید به ریشه در ارایه نهایی قرار میگیره نهایتن همه مرتب میشن
اگه متوجه نشدین بگید تا بیشتر توضیح بدم
(ظرفیت k ارایه میتونه یکسان نباشه برا فهم بیشتر اول بحث اینجوری توضیح دادم که حواستون بیشتر به طرف عمق مساله جلب بشه نه جزئیات ! فکر میکنم فن بیانم خوبه اگه باز جایی متوجه نشدی بگین)
سپاس بیکران.
(۱۲ بهمن ۱۳۹۱ ۰۷:۰۹ ب.ظ)teacherpc نوشته شده توسط: ظرفیت k تا ارایه همه یکسان هست رویهم ظرفیتشون میشه nممنون از وقتی که گذاشتین ولی این چیزی که شما می گین برای وقتیه که این K تا آرایمون مرتب باشن ولی اینجا که مرتب نیستند .شما از تکراری بودن عناصر آرایه چه استفاده ای تو حل کردین
عناصر هر کدوم از این k ارایه مرتب نیست یعنی k تا ارایه داریم که تو خودشون هم نامرتب هستند
خب حالا ما با عناصر بالای ارایه های (k تا ارایه رو به شکل پشته تصور کن که از بالای هرکدوم یه عنصر میاد بیرون و یه درخت ساخته میشه با عنصر شماره یکم بالای این k ارایه ) خب بعد از اینکه درخت ساخته شد دیگه کار تمامه هر بار هر ارایه ای که مینیمم بود عنصربالای خودش(به شکل پشته تصور کنیدش برااینکه متوجه شید ولی پشته نیستا حواست باشه!) را میفرسته تو درخت و این عنصر ارتفاع درخت رو طی میکنه(min تزریق میشه تو درخت ) و چون n عنصر داریم هر عنصر مجبوره از ارتفاع درخت طی کنه هر عنصری زودتر رسید به ریشه در ارایه نهایی قرار میگیره نهایتن همه مرتب میشن
اگه متوجه نشدین بگید تا بیشتر توضیح بدم
(ظرفیت k ارایه میتونه یکسان نباشه برا فهم بیشتر اول بحث اینجوری توضیح دادم که حواستون بیشتر به طرف عمق مساله جلب بشه نه جزئیات ! فکر میکنم فن بیانم خوبه اگه باز جایی متوجه نشدی بگین)
اگه این جوری باشه که شما میگین میشه هر آرایه ای را با nlogk مرتب کرد!
اگه میشه بیشتر توضیح بدین ممنون.اگه کسه دیگه ای هم میدونه خواهشا بگه .
اشتباه کردید
رو صورت سوال دقت کنید ببینید باز دقت کن یه بار دیگه صورت سوال رو بخون
گفته دنباله ای از اعداد که تعدادشون n تاست ولی k عنصر متمایز داریم (k<n)اگه k تا متمایز نبودند مشکل داشتیم و اینکه میگین اگه اینطور بود هر دنباله ای رو میشد با این روش مرتب کرد اصلن صحیح نیست (اینجا k عنصر متمایز داریم نه nتا متمایز!!!! )
خب من وقتی میدونم k عنصر متمایز دارم با ساخت درخت که ارتفاعش logk هست میام تمام n عنصر رو با log مقایسه مرتب میکنم
n تا عنصر داریم با log n مقایسه برا هر عنصر داریم میشه nlogk
فکر کنم هنوز صورت سوال رو خوب متوجه نشده باشین!
براخودم هم بعضی وقتا پیش اومده وقتی یه سوال رو خوب نخوندم با هر بار خوندن نکته جدیدی تو سوال کشف کردم!
شایدم اینجا من خوب متوجه نشدم!
(۱۴ بهمن ۱۳۹۱ ۱۱:۳۷ ق.ظ)teacherpc نوشته شده توسط: اشتباه کردیدنه ، این چیزی که میگین درست نیست.خوب ما تکراری داشته باشیم ولی مرتب که نیست پس با درخت انتخابی نمیشه.کس دیگه ای از دوستان نظری نداره؟
رو صورت سوال دقت کنید ببینید باز دقت کن یه بار دیگه صورت سوال رو بخون
گفته دنباله ای از اعداد که تعدادشون n تاست ولی k عنصر متمایز داریم (k<n)اگه k تا متمایز نبودند مشکل داشتیم و اینکه میگین اگه اینطور بود هر دنباله ای رو میشد با این روش مرتب کرد اصلن صحیح نیست (اینجا k عنصر متمایز داریم نه nتا متمایز!!!! )
خب من وقتی میدونم k عنصر متمایز دارم با ساخت درخت که ارتفاعش logk هست میام تمام n عنصر رو با log مقایسه مرتب میکنم
n تا عنصر داریم با log n مقایسه برا هر عنصر داریم میشه nlogk
فکر کنم هنوز صورت سوال رو خوب متوجه نشده باشین!
براخودم هم بعضی وقتا پیش اومده وقتی یه سوال رو خوب نخوندم با هر بار خوندن نکته جدیدی تو سوال کشف کردم!
شایدم اینجا من خوب متوجه نشدم!
این اخرین پاسخ من به این تاپیک هست شما که میگین استباهه درستش رو بزارید!
دیگه بیشتر نمیدونم من دیگه این بحث رو ادامه نمیدم
موفق باشید .
(۱۴ بهمن ۱۳۹۱ ۱۱:۳۷ ق.ظ)teacherpc نوشته شده توسط: خب من وقتی میدونم k عنصر متمایز دارم با ساخت درخت که ارتفاعش logk هست میام تمام n عنصر رو با log مقایسه مرتب میکنمteacherpc و m-m-m
n تا عنصر داریم با log n مقایسه برا هر عنصر داریم میشه nlogk
شایدم اینجا من خوب متوجه نشدم!
من مشکلو پیدا کردم.اشکال به صورت سوال و برداشت دوگانه از آن باز میگردد؛
راه حل teacherpc درست است به شرطی که ما از این k عدد تکراری خبر داشته باشیم، یعنی بدونیم که چهار تا عدد تکراری داریم و این اعداد مثلا ۶و ۷و ۸ و ۹ هستن.
-----------
اما وقتی فقط تعداد اعداد تکراری یا همون k رو بدونیم و اطلاعی راجع به اینکه این اعداد تکراری، چه اعدادی هستند نداشته باشیم اونوقت این راه حل جواب نمیدهد.
--------------
صورت این سوال دوپهلو است و مشخص نیست که آیا حالت اولی که توضیح دادم مدنظره یا حالت دوم.
------------------
با توجه به کلید سنجش، ظاهرا منظور طراح حالت اول بوده و در واقع ما از اینکه چه اعدادی تکراری هستن خبر داریم.
------------------
بنابراین این راه حل صحیح است که:
با k عنصر تکراری، درخت میسازیم و بعد n تا عنصر را جست و جو میکنیم(هر عنصر با logk) و در نهایت میشود nlogk.
----------------------
با سپاس از teacherpc
خوب،سوال که مشخصه وقتی نگفته میدونیم این k تا تکراری چه اعدادی هستند یعنی نمیدونیم .این که دیگه پیچوندن نداره هر چی تو سوال نگفته رو نمی دونیم چی هست.
در ضمن من اگه جواب سوالو میدونستم که اینجا مطرح نمی کردم .در ضمن آدم نباید از این که میگن راهش غلطه ناراحت بشه که
برای حل این سوال می تونید از به BST استفاده کنید و عناصر رو به ترتیب وارد BST کنید.فقط فرقی که داره اینه که وقتی یه عنصر تکراری وارد می کنید به جای اینکه اون رو ندیده بگیرید در نود مورد نظرش به یه عدد در نظر می گیرید و هر بار که تکرار شد یکی به اون عدد اضافه می کنید. ارتفاع این درخت به طور میانگین میشه logk. اگرم میگید که درخت مورب بشه میشه k می تونید از درخت AVL استفاده کنید. پس مجموعا n عنصر رو وارد می کنید و ارتفاع درخت هم متناسب با logk هست پس وارد کردنش در درخت میشه nlogk. در نهایت هم می تونید با یه پیمایش میانترتیب روی درخت مرتب شده ی اعداد رو به دست بیارید با این تفاوت که هر بار که میخواید مقدار نود رو چاپ کنید به تعدادی که در اون نود مشخص شده عدد رو چاپ می کنید که میشه n.
پس مجموعا میشه n + nlogk که میشه nlogk