۰
subtitle
ارسال: #۱
  
علوم کامپیوتر - سراسری ۸۸
با عرض سلام
دوستان برای مسئله ی زیر می تونیم بگیم چون جست و جو بر اساس کلید عناصر انجام می شه، ابتدا تمام عناصر را با روش درهم سازی در یک آرایه ی درهم ساز دخیره کنیم (مرتبه ی n) و سپس برای تمامی عناصر، کلید (x-y) رو جست و جو کنیم که می شه n عمل با هزینه ی یک، پس می شه از مرتبه ی n . پس جواب کل از مرتبه ی n هست. ( این روش رو امروز از یکی از دوستان مانشتی یاد گرفتم).
با تشکر
دوستان برای مسئله ی زیر می تونیم بگیم چون جست و جو بر اساس کلید عناصر انجام می شه، ابتدا تمام عناصر را با روش درهم سازی در یک آرایه ی درهم ساز دخیره کنیم (مرتبه ی n) و سپس برای تمامی عناصر، کلید (x-y) رو جست و جو کنیم که می شه n عمل با هزینه ی یک، پس می شه از مرتبه ی n . پس جواب کل از مرتبه ی n هست. ( این روش رو امروز از یکی از دوستان مانشتی یاد گرفتم).
با تشکر
۱
ارسال: #۲
  
RE: علوم کامپیوتر - سراسری ۸۸
سلام و وقت بخیر ...
بله به روش درهم سازی به صورت [tex]Binary\: Hash\: Map\: [/tex] در زمان خطی میتوان به این سوال پاسخ داد ، دقت کنیم که در این روش ابتدا باید عنصر [tex]x[/tex] را با مرتبه خطی یافت و سپس عملیات را انجام داد .
یک توضیح کوتاه در مورد [tex]Binary\: Hash\: Map\: [/tex] این ایده که در متن کتاب CLRS ذکر شده به این شکل است که ابتدا یک آرایه [tex]Boolean[/tex] ( ما فرض میکنیم ۰ و یک ها ) ایجاد میکنیم و برای هر عنصر مانند [tex]y[/tex] در آرایه مقدار [tex]BinaryMap[y][/tex] را یک میکنیم و در انتهای باقی مدخل ها را صفر در نظر میگیریم . ( هندلینگ طول آرایه مهم است )
بله به روش درهم سازی به صورت [tex]Binary\: Hash\: Map\: [/tex] در زمان خطی میتوان به این سوال پاسخ داد ، دقت کنیم که در این روش ابتدا باید عنصر [tex]x[/tex] را با مرتبه خطی یافت و سپس عملیات را انجام داد .
یک توضیح کوتاه در مورد [tex]Binary\: Hash\: Map\: [/tex] این ایده که در متن کتاب CLRS ذکر شده به این شکل است که ابتدا یک آرایه [tex]Boolean[/tex] ( ما فرض میکنیم ۰ و یک ها ) ایجاد میکنیم و برای هر عنصر مانند [tex]y[/tex] در آرایه مقدار [tex]BinaryMap[y][/tex] را یک میکنیم و در انتهای باقی مدخل ها را صفر در نظر میگیریم . ( هندلینگ طول آرایه مهم است )
۰
ارسال: #۳
  
RE: علوم کامپیوتر - سراسری ۸۸
مرسی که سوال داده الگوریتم میذارید. ادم با ایده های بقیه هم اشنا میشه.....
(۲۶ فروردین ۱۳۹۶ ۰۵:۴۷ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر ...
بله به روش درهم سازی به صورت [tex]Binary\: Hash\: Map\: [/tex] در زمان خطی میتوان به این سوال پاسخ داد ، دقت کنیم که در این روش ابتدا باید عنصر [tex]x[/tex] را با مرتبه خطی یافت و سپس عملیات را انجام داد .
یک توضیح کوتاه در مورد [tex]Binary\: Hash\: Map\: [/tex] این ایده که در متن کتاب CLRS ذکر شده به این شکل است که ابتدا یک آرایه [tex]Boolean[/tex] ( ما فرض میکنیم ۰ و یک ها ) ایجاد میکنیم و برای هر عنصر مانند [tex]y[/tex] در آرایه مقدار [tex]BinaryMap[y][/tex] را یک میکنیم و در انتهای باقی مدخل ها را صفر در نظر میگیریم . ( هندلینگ طول آرایه مهم است )
اگه میشه این نوع هشو بیشتر توضیح بدید...
۰
ارسال: #۴
  
RE: علوم کامپیوتر - سراسری ۸۸
اختیار دارید
مرسی از شما دوستان گرامی که همیشه کمک و راهنما هستید
موفق باشید
مرسی از شما دوستان گرامی که همیشه کمک و راهنما هستید
موفق باشید
۰
ارسال: #۵
  
RE: علوم کامپیوتر - سراسری ۸۸
اهان چون بازه مشخص نکرده نمیشه با شمارشی و سطلی و اینا رفت مجبوریم بعد از پارتیشن و افراز ،با مرتب سازی معمولی سورت کنیم.....
اون هشیم که من گفتم نمیشه رفت چون اون راه مرتبش واسه میانگین مرتبه زمانی میشه تتای n درعیر اینصورت میشه تتای n2.
اون هشیم که من گفتم نمیشه رفت چون اون راه مرتبش واسه میانگین مرتبه زمانی میشه تتای n درعیر اینصورت میشه تتای n2.
۰
ارسال: #۶
  
RE: علوم کامپیوتر - سراسری ۸۸
خوب اگه توی سوال قید نشه، منظورش میانگین هست فکر کنم. برای بهترین حالت یا بد ترین حالت قید می کنن توی سوال
ارسال: #۷
  
RE: علوم کامپیوتر - سراسری ۸۸
(۲۶ فروردین ۱۳۹۶ ۰۶:۵۳ ب.ظ)alimamala نوشته شده توسط: خوب اگه توی سوال قید نشه، منظورش میانگین هست فکر کنم. برای بهترین حالت یا بد ترین حالت قید می کنن توی سوال
نه اگه قید نشه منظورش بدترین حالت هست....اگه میانگین بخوان قید میکنن....
اگه روش اقای علیرضا درست باشه ،جواب این سوال غلط میشه.....
چرا من این سوالو تو پوران پیدا نمیکنم؟!
ارسال: #۸
  
RE: علوم کامپیوتر - سراسری ۸۸
(۲۶ فروردین ۱۳۹۶ ۰۶:۵۵ ب.ظ)*tarannom* نوشته شده توسط:(26 فروردین ۱۳۹۶ ۰۶:۵۳ ب.ظ)alimamala نوشته شده توسط: خوب اگه توی سوال قید نشه، منظورش میانگین هست فکر کنم. برای بهترین حالت یا بد ترین حالت قید می کنن توی سوال
نه اگه قید نشه منظورش بدترین حالت هست....اگه میانگین بخوان قید میکنن....
اگه روش اقای علیرضا درست باشه ،جواب این سوال غلط میشه.....
چرا من این سوالو تو پوران پیدا نمیکنم؟!
سلام . این روش حل به ایده Partition در مورد مرتب سازی سریع اشاره میکنه که عناصر کوچکتر از x رو در مرتبه خطی پیدا میکنه و اونا رو مرتب میکنه ، خوب بدترین حالت اینه که n-1 عنصر کوچکتر از x باشند و برای مرتب سازی اونا به [tex](n-1)\log(n-1)=O(nlogn)[/tex] هزینه نیاز داریم و اکنون به روش جستجوی باینری میتوان این دو عدد رو یافت .. ( گزینه ۳ ) روشی که بنده گفتم در صورتیی که مجاز به درهم سازی باشیم کاربرد دارد و همچنین بازه اعداد داده شده محدود باشه ( فضا مهم نباشه ) ( البته میشه با یک تابع ابتکار مناسب و نگاشت های هوشمندانه این مساله رو هندلینگ کرد )
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close