(۰۹ بهمن ۱۳۹۲ ۰۵:۲۷ ب.ظ)masoud67 نوشته شده توسط:  آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟

پوران دقیقا همینو گفته . درسته

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

(09 بهمن ۱۳۹۲ ۰۵:۲۷ ب.ظ)masoud67 نوشته شده توسط:  آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟

پوران دقیقا همینو گفته . درسته

دقیقا چون پوران اینو گفته شک کردم.

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

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

(09 بهمن ۱۳۹۲ ۰۵:۲۷ ب.ظ)masoud67 نوشته شده توسط:  آیا این چیزی که میگم در مورد این مسئله صحیحه.
اول باید فعالیت ها را بر اساس ارزشها مرتب کنیم که میشه nlogn
و بعد به ترتیب ارزش ها ، انتخاب میکنیم و امکان سنجی (نمیدونم دقیقا به این مرحله چی میگن) انجام میدیم که این امکان سنجی میشه n به توان ۲
و در کل مرتبه میشه nlogn + n^2
درست گفتم ؟

پوران دقیقا همینو گفته . درسته

دقیقا چون پوران اینو گفته شک کردم.

اما از اونجا که مقسمی تایید کرده و توی Clrs هم چیزی گفته نشده ، دیگه مشکلی نمیمونه و درسته

چرا بدون مهلت معین مرتب سازی رو میذارن nlogn!
مگه با مرتب سازی شمارشی نمیشه انجام داد؟!!

Sent from my SM-T210R using Tapatalk

(۰۹ بهمن ۱۳۹۲ ۰۶:۳۳ ب.ظ)hoomanab نوشته شده توسط:  چرا بدون مهلت معین مرتب سازی رو میذارن nlogn!
مگه با مرتب سازی شمارشی نمیشه انجام داد؟!!

شاید زمانها عدد طبیعی نباشن.

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 میشه
امیدوارم منظور رو رسونده باشم