آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟
(۰۹ بهمن ۱۳۹۲ ۰۵:۲۷ ب.ظ)masoud67 نوشته شده توسط: آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟
پوران دقیقا همینو گفته . درسته
(۰۹ بهمن ۱۳۹۲ ۰۵:۳۳ ب.ظ)Saoshiyant نوشته شده توسط:دقیقا چون پوران اینو گفته شک کردم.(09 بهمن ۱۳۹۲ ۰۵:۲۷ ب.ظ)masoud67 نوشته شده توسط: آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟
پوران دقیقا همینو گفته . درسته
چرا بدون مهلت معین مرتب سازی رو میذارن nlogn!
مگه با مرتب سازی شمارشی نمیشه انجام داد؟!!
Sent from my SM-T210R using Tapatalk
(۰۹ بهمن ۱۳۹۲ ۰۶:۳۳ ب.ظ)hoomanab نوشته شده توسط: چرا بدون مهلت معین مرتب سازی رو میذارن nlogn!شاید زمانها عدد طبیعی نباشن.
مگه با مرتب سازی شمارشی نمیشه انجام داد؟!!
(۰۹ بهمن ۱۳۹۲ ۰۵:۴۳ ب.ظ)masoud67 نوشته شده توسط:(09 بهمن ۱۳۹۲ ۰۵:۳۳ ب.ظ)Saoshiyant نوشته شده توسط:دقیقا چون پوران اینو گفته شک کردم.(09 بهمن ۱۳۹۲ ۰۵:۲۷ ب.ظ)masoud67 نوشته شده توسط: آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟
پوران دقیقا همینو گفته . درسته
اما از اونجا که مقسمی تایید کرده و توی Clrs هم چیزی گفته نشده ، دیگه مشکلی نمیمونه و درسته
nlogn سریعترین زمان حل این مسئله هستش
(۱۰ بهمن ۱۳۹۲ ۰۱:۳۳ ق.ظ)keywan78 نوشته شده توسط: nlogn سریعترین زمان حل این مسئله هستشحالت خاصی هست یا کلی میگید؟
آخه واسه بررسی امکان پذیری باید n به توان ۲ هزینه صرف کرد
(۱۰ بهمن ۱۳۹۲ ۰۱:۳۵ ق.ظ)masoud67 نوشته شده توسط:(10 بهمن ۱۳۹۲ ۰۱:۳۳ ق.ظ)keywan78 نوشته شده توسط: nlogn سریعترین زمان حل این مسئله هستشحالت خاصی هست یا کلی میگید؟
آخه واسه بررسی امکان پذیری باید n به توان ۲ هزینه صرف کرد
نه اگه توی مرحله امکان سنجیش بجای ارایه از disjoint-set استفاده بشه بهینه تر میشه و با nlogn قابل حل
(۱۰ بهمن ۱۳۹۲ ۰۱:۵۹ ق.ظ)keywan78 نوشته شده توسط:اینو خبر نداشتم. باید یه تحقیقی در موردش بکنم(10 بهمن ۱۳۹۲ ۰۱:۳۵ ق.ظ)masoud67 نوشته شده توسط:(10 بهمن ۱۳۹۲ ۰۱:۳۳ ق.ظ)keywan78 نوشته شده توسط: nlogn سریعترین زمان حل این مسئله هستشحالت خاصی هست یا کلی میگید؟
آخه واسه بررسی امکان پذیری باید n به توان ۲ هزینه صرف کرد
نه اگه توی مرحله امکان سنجیش بجای ارایه از disjoint-set استفاده بشه بهینه تر میشه و با nlogn قابل حل
میدونستم این پوران هیچ جمله درستی را ، با یه غلط نهفته درونش نمینویسه
تشکر
(۱۰ بهمن ۱۳۹۲ ۰۱:۵۹ ق.ظ)keywan78 نوشته شده توسط:(10 بهمن ۱۳۹۲ ۰۱:۳۵ ق.ظ)masoud67 نوشته شده توسط:(10 بهمن ۱۳۹۲ ۰۱:۳۳ ق.ظ)keywan78 نوشته شده توسط: nlogn سریعترین زمان حل این مسئله هستشحالت خاصی هست یا کلی میگید؟
آخه واسه بررسی امکان پذیری باید n به توان ۲ هزینه صرف کرد
نه اگه توی مرحله امکان سنجیش بجای ارایه از disjoint-set استفاده بشه بهینه تر میشه و با nlogn قابل حل
ببخشید یعنی چطوری؟؟
(۱۰ بهمن ۱۳۹۲ ۰۳:۳۱ ق.ظ)Good! نوشته شده توسط: ببخشید یعنی چطوری؟؟
یک ساختمان دادست که بر روی مجموعه ها تعریف شده.
سه کار زیر روی اونها تعریف شده:
ساختن
جستجو کردن
الحاق شدن
حالا ما ک می خوایم مجموعه ای از کارها را بررسی کنیم ساختمان داده ای این شکلی با کمی تغییرات درست می کنیم و وقتی یک کار امکان سنجی شد و با یکی از مجموع های ما داشت به همدیگه الحاق میشن .
یه مثال
{۱۰} {۸۹} {۷} {۵۶} {۴} {۱۲۳}
مهلت های ۱۰ و ۷ و ۴ هنوز ارضا نشدن
اگه در این لحظه مهلت ۴ ارضا بشه
اولش مجموعه {۴} پدر مجموعه {۵۶} میشه و بعد از اون مجموعه جدید {۴۵۶} فرزند {۱۲۳} و مجموعه بزرگتر {۱۲۳۴۵۶} ایجاد میشه.
مرتبه زمانیش در بدترین حالت nlogn میشه
امیدوارم منظور رو رسونده باشم