سلام دوستان مدرسان جواب اینو nlogn داده.یعنی اول مرتبش کرده..مگر ما نمیتونیم با یه جدول درهم سازی که در زمان n ساخته میشه درایه هارو بریزیم داخل جدول و با هر اظافه شدن به یه سطر یه شمارنده اضاف کنیم.حالا با یه پیمایش جدول تعداد تکرار هارو بدست میاریم.یعنی در زمان n .درسته؟
![[تصویر: 324847_866906716941be30b85ca645b0175a64.jpg]](https://img.manesht.ir/324847_866906716941be30b85ca645b0175a64.jpg)
منم همین فکر رو کردم وولی نمیدونم چرا مدرسان جان فرموندن نمیشه
(۱۳ دى ۱۳۹۳ ۱۱:۱۶ ب.ظ)sana70 نوشته شده توسط: ببینید شما میتونید با log nآرایه رو مرتب کنید ,خوب وقتی آرایه مرتب هست عناصر مشابه هم پشت سر هم هستند دیگه و دسترسی به n امین عنصر هم از مرتبه اوی ان هست
هیچ الگوریتم مرتب سازی کمتر از nlogn نیست و این رو درخت تصمیم هم ثابت می کنه
به نظر من چون تعداد عناصری که دنبالش میگردیم ممکن زیاد باشه پس ارزش مرتب کردن و پیدا کردنشون بهتر از اینه که هر دفعه بصورت خطی و مرتبه n دنبالش بگردیم
و مرتبه مرتب سازی هم که در حالت متوسط nlogn است.
(۱۳ دى ۱۳۹۳ ۰۹:۵۷ ب.ظ)kefsan نوشته شده توسط: منم همین فکر رو کردم وولی نمیدونم چرا مدرسان جان فرموندن نمیشه
بیخودی که نگفته حقیقی
وقتی میگه حقیقی هش نمیشه و مجبورین مرتب کنین
اگر اعداد صحیح بود یا رنج داشت بله هش میشد وقتی اعداد محدودیت ندارن اونوقت مرتب سازی مقایسه ایی دوستان عزیز ببخشید
سلام.میشه درباره حقیقی بودن بیشتر توضیح بدید.ممنون میشم
(۱۳ دى ۱۳۹۳ ۰۷:۲۴ ب.ظ)MR.oracle نوشته شده توسط: سلام دوستان مدرسان جواب اینو nlogn داده.یعنی اول مرتبش کرده..مگر ما نمیتونیم با یه جدول درهم سازی که در زمان n ساخته میشه درایه هارو بریزیم داخل جدول و با هر اظافه شدن به یه سطر یه شمارنده اضاف کنیم.حالا با یه پیمایش جدول تعداد تکرار هارو بدست میاریم.یعنی در زمان n .درسته؟این سوال باید بازه اعداد حقیقی رو مشخص میکرد و میگفت که 'کا' بزرگتر از صفر و کوچکتر مساوی إن هستش
استفاده از درهم سازی در صورتی امکانپذیر که سوال اجازه دسترسی به حافظه ای به اندازه On و همچنین پیش پردازشی به اندازه On رو به شما بده
اگر تعداد تکرارها وابسته به إن باشه مرتبه زمانی nlgk که در این سوال وابستس ولی اگه وابسته نبود nlgn ; مشابه سوال هشتادشش فصل دو کتاب۶۰۰ مسئله
اگر یه آرایه
n عضوی
داشته باشیم که اندیسش مقدار درایه ها باشه
میشه با یه بار پیمایش لیست و اینکریز یه واحدی یه لیست از تکرارا داشت و به بارم اون لیست رو پیمایش کنیم و دنبال خمینی تو سوال گفته بگردیم
من این کارو تو برنامه نویسی زیاد انجام میدم
سوالش ناقصه باید محدودیت هارو بگه
a[2]=5
یعنی عدد ۲ توی لیست ۵ بار تکرار شده مثلا
بچه ها الان k یه عدد منفی باشه دقیقا چه اتفاقی میفته؟؟؟
مرسی از دوستان..پس چون گفته حقیقی نه میشه از آرایه اضافی رفت نه از هش..چون شاید عدد ۱/۵ داشته باشیم..درسته؟
بچه ها میشه بگید دقیقا کی مجازیم از هش استفاده کنیم؟؟؟؟اصلا شرایط خاصی داره؟؟
(۱۴ دى ۱۳۹۳ ۰۱:۴۳ ق.ظ)miladcr7 نوشته شده توسط: سلام.میشه درباره حقیقی بودن بیشتر توضیح بدید.ممنون میشم
اگر زنج اعدا شما با فاصله های خیلی زیاد باشه مثلا اعداد رادیکالی.... اونوقت تایع درهم ساز هم خوب نمیتونه مکاشفه کنه و اعداد رو خوب ادرس دهی کنه اگر اعداد صحیح باشن اونوقت با روش شمارشی و یه تابع در هم سازی خوب میشه یه هش خطی ساخت