27 بهمن 1395, 02:50 ب.ظ
27 بهمن 1395, 09:09 ب.ظ
(27 بهمن 1395 02:50 ب.ظ)alireza01 نوشته شده توسط: [ -> ]
ممنون .
با [tex]\theta(n)[/tex] میشه مرتب کرد.
با پیمایش روی همه‌ی اعداد، تعداد هر عدد رو در یک Hashmap نگه می‌داریم. کافی است به هر عدد که می‌رسیم، بررسی کنیم اگر در مپ وجود نداشت، اضافه کنیم. اگر وجود داشت، value آن را یک واحد زیاد کنیم. مرتبه‌ی پیمایش روی کلیه‌ی اعداد [tex]\theta(n)[/tex] است.
طول (تعداد کلیدهای) مپ ماکزیمم [tex]k = \log(n)[/tex] است چرا که ماکزیمم این تعداد عدد متفاوت داریم. این k عددِ متمایز را می‌توان از مرتبه‌ی [tex]\theta(klog(k))=\theta(\log n\times\log(\log n))[/tex] که چون از [tex]\theta(n)[/tex] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش میکنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.
27 بهمن 1395, 09:52 ب.ظ
(27 بهمن 1395 09:09 ب.ظ)Pure Liveliness نوشته شده توسط: [ -> ]ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟(27 بهمن 1395 02:50 ب.ظ)alireza01 نوشته شده توسط: [ -> ]
ممنون .
با [tex]\theta(n)[/tex] میشه مرتب کرد.
با پیمایش روی همه‌ی اعداد، تعداد هر عدد رو در یک Hashmap نگه می‌داریم. کافی است به هر عدد که می‌رسیم، بررسی کنیم اگر در مپ وجود نداشت، اضافه کنیم. اگر وجود داشت، value آن را یک واحد زیاد کنیم. مرتبه‌ی پیمایش روی کلیه‌ی اعداد [tex]\theta(n)[/tex] است.
طول (تعداد کلیدهای) مپ ماکزیمم [tex]k = \log(n)[/tex] است چرا که ماکزیمم این تعداد عدد متفاوت داریم. این k عددِ متمایز را می‌توان از مرتبه‌ی [tex]\theta(klog(k))=\theta(\log n\times\log(\log n))[/tex] که چون از [tex]\theta(n)[/tex] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش میکنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.
تقریبا شبیه روش مرتب سازی شمارشی نیست؟
27 بهمن 1395, 10:08 ب.ظ
(27 بهمن 1395 09:52 ب.ظ)msour44 نوشته شده توسط: [ -> ]به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب میکنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\log(n))[/tex] در حالی که در مرتب‌سازی شمارشی همون [tex]\theta(n)[/tex] میشد.(27 بهمن 1395 09:09 ب.ظ)Pure Liveliness نوشته شده توسط: [ -> ]ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟(27 بهمن 1395 02:50 ب.ظ)alireza01 نوشته شده توسط: [ -> ]
ممنون .
با [tex]\theta(n)[/tex] میشه مرتب کرد.
با پیمایش روی همه‌ی اعداد، تعداد هر عدد رو در یک Hashmap نگه می‌داریم. کافی است به هر عدد که می‌رسیم، بررسی کنیم اگر در مپ وجود نداشت، اضافه کنیم. اگر وجود داشت، value آن را یک واحد زیاد کنیم. مرتبه‌ی پیمایش روی کلیه‌ی اعداد [tex]\theta(n)[/tex] است.
طول (تعداد کلیدهای) مپ ماکزیمم [tex]k = \log(n)[/tex] است چرا که ماکزیمم این تعداد عدد متفاوت داریم. این k عددِ متمایز را می‌توان از مرتبه‌ی [tex]\theta(klog(k))=\theta(\log n\times\log(\log n))[/tex] که چون از [tex]\theta(n)[/tex] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش میکنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.
تقریبا شبیه روش مرتب سازی شمارشی نیست؟
27 بهمن 1395, 11:44 ب.ظ
(27 بهمن 1395 10:08 ب.ظ)Behnam نوشته شده توسط: [ -> ]ممنون از پاسختان(27 بهمن 1395 09:52 ب.ظ)msour44 نوشته شده توسط: [ -> ]به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب میکنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\log(n))[/tex] در حالی که در مرتب‌سازی شمارشی همون [tex]\theta(n)[/tex] میشد.(27 بهمن 1395 09:09 ب.ظ)Pure Liveliness نوشته شده توسط: [ -> ]ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟(27 بهمن 1395 02:50 ب.ظ)alireza01 نوشته شده توسط: [ -> ]
ممنون .
با [tex]\theta(n)[/tex] میشه مرتب کرد.
با پیمایش روی همه‌ی اعداد، تعداد هر عدد رو در یک Hashmap نگه می‌داریم. کافی است به هر عدد که می‌رسیم، بررسی کنیم اگر در مپ وجود نداشت، اضافه کنیم. اگر وجود داشت، value آن را یک واحد زیاد کنیم. مرتبه‌ی پیمایش روی کلیه‌ی اعداد [tex]\theta(n)[/tex] است.
طول (تعداد کلیدهای) مپ ماکزیمم [tex]k = \log(n)[/tex] است چرا که ماکزیمم این تعداد عدد متفاوت داریم. این k عددِ متمایز را می‌توان از مرتبه‌ی [tex]\theta(klog(k))=\theta(\log n\times\log(\log n))[/tex] که چون از [tex]\theta(n)[/tex] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش میکنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.
تقریبا شبیه روش مرتب سازی شمارشی نیست؟
چرا در hash تعداد مدخل ها رو لگاریتم n میگیرد نباید به اندازه بزرگترین عدد موجود در ارایه باشه که ممکنه نسبت به n نمایی باشه؟منظورم اینکه اندیس ها نباید اعداد متوالی باشه ؟درست n عدد داریم با ضریب تکرار لگاریتمی ولی اگه از Hashاستفاده کنیم برای ذخیره تعداد تکرار هر عدد نباید اندیس رو عدد و درایه ان را تعداد تکرار تصور کنیم منظورت چیز دیگری است؟
ببخشید که وقت تونو میگیرم ولی اگه اشتباه نکنم این تست سال ۸۹ نرم افزاره که هادی یوسفی جوابشو گزینه ۳ گفته به این صورت که با nعدد داده شده یک BST متوازن می سازیم ولی در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت loglogn میشه و مرتبه ساخت n.loglogn سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل میشه n.loglogn مدرسان هم همین گزینه رو گفته با همین استدلال تقریبا مشابه با هادی یوسفی.
ولی روشی که من این تست و اولین بار جواب دادم این بود که می توان از متن سوال پی برد که logn لیست مرتب شده با توجه به تکرار هر عدد در بدترین حالت داریم و اینکه مرتبه ادغام kلیست مرتب در حداقل n.logk است پس مرتبه کل میشه n.loglogn
موفق باشید
28 بهمن 1395, 12:22 ق.ظ
(27 بهمن 1395 11:44 ب.ظ)msour44 نوشته شده توسط: [ -> ]ممنون از پاسختانتوی hash map اعدادی که یکی هستن توی یه خونه نگاشت میشن در نتیجه تمامی اعداد یکسان در یک خونه هستن و چون توی صورت سوال گفته حداکثر تعداد اعداد یکسان [tex]\log n[/tex] تا هست در هر مدخل نهایتا به همین مقدار عدد وجود داره.
چرا در hash تعداد مدخل ها رو لگاریت n میگیرد نباید به اندازه بزرگترین عدد موجود در ارایه باشه که ممکنه نسبت به n نمایی باشه؟منظورم اینکه اندیس ها نباید اعداد متوالی باشه ؟درست n عدد داریم با ضریب تکرار لگاریتمی ولی اگه از Hashاستفاده کنیم برای ذخیره تعداد تکرار هر عدد نباید اندیس رو عدد و درایه ان را تعداد تکرار تصور کنیم منظورت چیز دیگری است؟
ببخشید که وقت تونو میگیرم ولی اگه اشتباه نکنم این تست سال ۸۹ نرم افزاره که هادی یوسفی جوابشو گزینه ۳ گفته به این صورت که با nعدد داده شده یک BST متوازن می سازیم ولی در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت loglogn میشه و مرتبه ساخت n.loglogn سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل میشه n.loglogn مدرسان هم همین گزینه رو گفته با همین استدلال تقریبا مشابه با هادی یوسفی.
ولی روشی که من این تست و اولین بار جواب دادم این بود که می توان از متن سوال پی برد که logn لیست مرتب شده با توجه به تکرار هر عدد در بدترین حالت داریم و اینکه مرتبه ادغام kلیست مرتب در حداقل n.logk است پس مرتبه کل میشه n.loglogn
موفق باشید
نمیدونم باید نگاه کنم. روشی که گفتید منطقی هست اما روشی که من نوشتم هم منطقی هست با هزینه ی کمتر. نگاه میکنم مینویسم اینجا.
28 بهمن 1395, 03:09 ق.ظ
(27 بهمن 1395 11:44 ب.ظ)msour44 نوشته شده توسط: [ -> ](27 بهمن 1395 10:08 ب.ظ)Behnam نوشته شده توسط: [ -> ]ممنون از پاسختان(27 بهمن 1395 09:52 ب.ظ)msour44 نوشته شده توسط: [ -> ]به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب میکنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\log(n))[/tex] در حالی که در مرتب‌سازی شمارشی همون [tex]\theta(n)[/tex] میشد.(27 بهمن 1395 09:09 ب.ظ)Pure Liveliness نوشته شده توسط: [ -> ]ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟(27 بهمن 1395 02:50 ب.ظ)alireza01 نوشته شده توسط: [ -> ]
ممنون .
با [tex]\theta(n)[/tex] میشه مرتب کرد.
با پیمایش روی همه‌ی اعداد، تعداد هر عدد رو در یک Hashmap نگه می‌داریم. کافی است به هر عدد که می‌رسیم، بررسی کنیم اگر در مپ وجود نداشت، اضافه کنیم. اگر وجود داشت، value آن را یک واحد زیاد کنیم. مرتبه‌ی پیمایش روی کلیه‌ی اعداد [tex]\theta(n)[/tex] است.
طول (تعداد کلیدهای) مپ ماکزیمم [tex]k = \log(n)[/tex] است چرا که ماکزیمم این تعداد عدد متفاوت داریم. این k عددِ متمایز را می‌توان از مرتبه‌ی [tex]\theta(klog(k))=\theta(\log n\times\log(\log n))[/tex] که چون از [tex]\theta(n)[/tex] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش میکنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.
تقریبا شبیه روش مرتب سازی شمارشی نیست؟
چرا در hash تعداد مدخل ها رو لگاریتم n میگیرد نباید به اندازه بزرگترین عدد موجود در ارایه باشه که ممکنه نسبت به n نمایی باشه؟منظورم اینکه اندیس ها نباید اعداد متوالی باشه ؟درست n عدد داریم با ضریب تکرار لگاریتمی ولی اگه از Hashاستفاده کنیم برای ذخیره تعداد تکرار هر عدد نباید اندیس رو عدد و درایه ان را تعداد تکرار تصور کنیم منظورت چیز دیگری است؟
ببخشید که وقت تونو میگیرم ولی اگه اشتباه نکنم این تست سال ۸۹ نرم افزاره که هادی یوسفی جوابشو گزینه ۳ گفته به این صورت که با nعدد داده شده یک BST متوازن می سازیم ولی در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت loglogn میشه و مرتبه ساخت n.loglogn سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل میشه n.loglogn مدرسان هم همین گزینه رو گفته با همین استدلال تقریبا مشابه با هادی یوسفی.
ولی روشی که من این تست و اولین بار جواب دادم این بود که می توان از متن سوال پی برد که logn لیست مرتب شده با توجه به تکرار هر عدد در بدترین حالت داریم و اینکه مرتبه ادغام kلیست مرتب در حداقل n.logk است پس مرتبه کل میشه n.loglogn
موفق باشید
اندازه‌ی داده‌ها (رِنجِ اعداد) زیاد مهم نیست و هندل میشه ولی چیزی که مهم هست احتمال رخ دادن بدترین حالت هست. مرتبه‌ی جستجو و درج در هش‌مپ در حالت میانگین [tex]\theta(1)[/tex] هست پس جستجو و درج n عنصر هم از مرتبه‌ی [tex]\theta(n)[/tex] خواهد بود.
ولی ممکن هست همه‌ی اعداد (کلیدها) تنها به یک خونه از هش‌مپ نگاشت بشن. اینکه دو (یا بیشتر) کلید مختلف به یک خونه نگاشت بشن طبیعی هست و اینا رو به صورت linkedlist نگه می‌دارند. در واقع بدترین برای درج یا جستجوی n عدد ممکنه [tex]O(n)[/tex]هم بشه که البته بسته به کلیدها (اگر کلیدها قابل مقایسه باشند) می‌توان به جای لیست به صورت درخت پیاده‌سازی کرد و بدترین حالت رو کرد [tex]O(\log n)[/tex] (بدترین حالت یعنی اینکه به ازای یک کلید، یک خونه برگردونده میشه ولی اون خونه بیش از یک value داره و باید کل آیتم‌هاش رو گشت).
از طرف دیگه برای n داده‌ی ورودی، با احتمال بیش از [tex]1-\frac{1}{n}[/tex] هیچ خونه‌ی هش‌مپ بیش از [tex]\log(n)[/tex] داده (مقدار) نخواهد داشت (که در اصل در این مسأله صرفا [tex]\log(n)[/tex] داده‌ی ورودی داریم، پس خونه‌های هش‌مپ بیش از [tex]\log(\log n)[/tex] مقدار نخواهند داشت که برای درج یا جستجوی n عنصر با ماکزیمم [tex]\log n[/tex] عنصر متفاوت در این سوال ماکزیمم مرتبه‌ی [tex]nlog(\log n)[/tex] خواهیم داشت ولی در کل، مخصوصاً با این تعدادِ کم داده‌ی متمایز مرتبه‌ی درج و جستجوی هش‌مپ رو [tex]O(1)[/tex] میگیرند.
و اما در مورد روش شما، نمیدونم از کجا گفتید لیست مرتب شده داریم. فرض کنید که [tex]\log(n)[/tex] عدد متمایز داریم و تعداد تکرار این اعداد هم بر فرض برابر هستند و به صورت نزولی اومدند، مثلا n=8 و در نتیجه 3 عدد متمایز داریم. فرض کنید به این صورت اومدند:
3,2,1,3,2,1,3,2,1,3,2,1
الان اینجا هیچ لیست مرتب شده وجود نداره که شما صرفاً ادغام کنید.
(28 بهمن 1395 02:52 ق.ظ)alireza01 نوشته شده توسط: [ -> ]سلام . نظر و جواب دوست عزیزمون Pure Liveliness رو قبول ندارم ، چون در صورت تست گفته شده که مرتب سازی باید مبتنی بر مقایسه باشه ، روش Hash که ایشون استفاده کردن حتی با بهترین تابع ابتکار باز هم ایده مقایسه ای نداره ( این ایده که در مدخل مورد نظر مقدار را افزایش یا وارد کنیم اصلا یک ایده مقایسه ای نیست ، این ایده در اصل همان روش مرتب سازی شمارشی است با یک تفاوت در طول بازه آن و تابع ابتکار ) ، لیست بیشتر الگوریتم هایی که مبتنی بر مقایسه هستند رو بنده استخراج کردم که در جدول زیر میبینید که بهترین زمان متوسط همان [tex]\theta(nlogn)[/tex] است .
روشی که میشه بهش استناد کرد اینه که ما حداکثر [tex]\log n[/tex] عدد متمایز داریم ، یک آرایه دو بعدی کمکی به نام TEMP به همین طول تولید کرده و با مرتبه زمانی [tex]O(n)[/tex] اعداد منحصر به فرد به پیدا کرده و به همراه فرکانس ( تعداد تکرار های آنها ) درون آرایه جدید قرار میدهیم . حال ما [tex]\log n[/tex] عدد داریم ، با هزینه [tex]nlog(\log n)[/tex] آرایه جدید را مرتب میکنیم . سپس بر اساس فرکانس آنها را در آرایه قبلی وارد میکنیم که مرتبه زمانی کلی برابر است با [tex]\theta(nloglogn\: +\: n)\: =\: \theta(nloglogn)[/tex] است .
اگر اشتباه میکنم خوشحال میشم بفرمایید . از پاسخم مطمعن نیستم .
این لزوماً درست نیست که مقایسه‌ای نمیتونه از [tex]\theta(nlogn)[/tex] بهتر باشه وقتی توو صورت سؤال برای توزیع داده‌ها شرط گذاشته. مسائل زیادی وجود داره که مثلا اعداد مسأله در قالب لیست‌های مرتب شده‌ی هم‌اندازه یا غیرهم‌اندازه و ... هستند که بسته به نوع سوال میشه از روش مقایسه‌ای استفاده کرد و مرتبه‌های مختلفی داشت.
ضمناً روش شما دقیقاً همون روش ایشون هست با این تفاوت که صرفاً شما اومدید نحوه‌ی پیاده‌سازی تابع هش‌مپ رو به صورت آرایه درآوردید که در این صورت اندازه‌ی آرایه‌تون باید در ابعاد (رِنج) n باشه که ممکن هست عملی نباشه. ممکن هست شما صرفاً فقط دو عدد متمایز داشته باشید ولی بازه‌ی اون‌ها بزرگ باشه (مثلا یکی 0 و یکی [tex]10^{12}[/tex]).
28 بهمن 1395, 03:30 ق.ظ
ممنون از وقت گذاشتن و پاسخگویی تون ، نمیدونم چرا پستم پاک شد.
28 بهمن 1395, 04:06 ق.ظ
(28 بهمن 1395 03:30 ق.ظ)alireza01 نوشته شده توسط: [ -> ]ممنون از وقت گذاشتن و پاسخگویی تون ، نمیدونم چرا پستم پاک شد.
من هم تعجب میکنم پستتون پاک شده، چون هیچ کدوم از مدیرها هم پاک نکردند (و الا متوجه میشدم).
به مدیر این بخش میگم بررسی کنه.
28 بهمن 1395, 04:10 ق.ظ
(28 بهمن 1395 03:30 ق.ظ)alireza01 نوشته شده توسط: [ -> ]ممنون از وقت گذاشتن و پاسخگویی تون ، نمیدونم چرا پستم پاک شد.خودتون حذف کردید. شاید دستتون خورده.
28 بهمن 1395, 04:34 ب.ظ
(28 بهمن 1395 03:09 ق.ظ)Behnam نوشته شده توسط: [ -> ]اینکه از کجا لیست های مرتب بدست میشه اورد به اینصورت که اگه تعداد اعداد متمایز رو logn بگیریم با فرض برابر بودن تعداد هر کدام یعنی اندازه هر لیست تقریبا سقف n/long است بعد از روش افراز مرتب سازی سریع به صورت تصادفی استفاده کنیم تا جایی که اندازه زیرلیست ها n/logn بشه می تونیم تمامی لیست های مرتب رو بدست بیاریم که هزینه افراز هم در این حالت nloglogn میشه بعد هم ادغام که هزینه اون هم n loglogn است(27 بهمن 1395 11:44 ب.ظ)msour44 نوشته شده توسط: [ -> ](27 بهمن 1395 10:08 ب.ظ)Behnam نوشته شده توسط: [ -> ]ممنون از پاسختان(27 بهمن 1395 09:52 ب.ظ)msour44 نوشته شده توسط: [ -> ]به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب میکنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\log(n))[/tex] در حالی که در مرتب‌سازی شمارشی همون [tex]\theta(n)[/tex] میشد.(27 بهمن 1395 09:09 ب.ظ)Pure Liveliness نوشته شده توسط: [ -> ]با [tex]\theta(n)[/tex] میشه مرتب کرد.ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟
با پیمایش روی همه‌ی اعداد، تعداد هر عدد رو در یک Hashmap نگه می‌داریم. کافی است به هر عدد که می‌رسیم، بررسی کنیم اگر در مپ وجود نداشت، اضافه کنیم. اگر وجود داشت، value آن را یک واحد زیاد کنیم. مرتبه‌ی پیمایش روی کلیه‌ی اعداد [tex]\theta(n)[/tex] است.
طول (تعداد کلیدهای) مپ ماکزیمم [tex]k = \log(n)[/tex] است چرا که ماکزیمم این تعداد عدد متفاوت داریم. این k عددِ متمایز را می‌توان از مرتبه‌ی [tex]\theta(klog(k))=\theta(\log n\times\log(\log n))[/tex] که چون از [tex]\theta(n)[/tex] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش میکنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.
تقریبا شبیه روش مرتب سازی شمارشی نیست؟
چرا در hash تعداد مدخل ها رو لگاریتم n میگیرد نباید به اندازه بزرگترین عدد موجود در ارایه باشه که ممکنه نسبت به n نمایی باشه؟منظورم اینکه اندیس ها نباید اعداد متوالی باشه ؟درست n عدد داریم با ضریب تکرار لگاریتمی ولی اگه از Hashاستفاده کنیم برای ذخیره تعداد تکرار هر عدد نباید اندیس رو عدد و درایه ان را تعداد تکرار تصور کنیم منظورت چیز دیگری است؟
ببخشید که وقت تونو میگیرم ولی اگه اشتباه نکنم این تست سال ۸۹ نرم افزاره که هادی یوسفی جوابشو گزینه ۳ گفته به این صورت که با nعدد داده شده یک BST متوازن می سازیم ولی در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت loglogn میشه و مرتبه ساخت n.loglogn سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل میشه n.loglogn مدرسان هم همین گزینه رو گفته با همین استدلال تقریبا مشابه با هادی یوسفی.
ولی روشی که من این تست و اولین بار جواب دادم این بود که می توان از متن سوال پی برد که logn لیست مرتب شده با توجه به تکرار هر عدد در بدترین حالت داریم و اینکه مرتبه ادغام kلیست مرتب در حداقل n.logk است پس مرتبه کل میشه n.loglogn
موفق باشید
اندازه‌ی داده‌ها (رِنجِ اعداد) زیاد مهم نیست و هندل میشه ولی چیزی که مهم هست احتمال رخ دادن بدترین حالت هست. مرتبه‌ی جستجو و درج در هش‌مپ در حالت میانگین [tex]\theta(1)[/tex] هست پس جستجو و درج n عنصر هم از مرتبه‌ی [tex]\theta(n)[/tex] خواهد بود.
ولی ممکن هست همه‌ی اعداد (کلیدها) تنها به یک خونه از هش‌مپ نگاشت بشن. اینکه دو (یا بیشتر) کلید مختلف به یک خونه نگاشت بشن طبیعی هست و اینا رو به صورت linkedlist نگه می‌دارند. در واقع بدترین برای درج یا جستجوی n عدد ممکنه [tex]O(n)[/tex]هم بشه که البته بسته به کلیدها (اگر کلیدها قابل مقایسه باشند) می‌توان به جای لیست به صورت درخت پیاده‌سازی کرد و بدترین حالت رو کرد [tex]O(\log n)[/tex] (بدترین حالت یعنی اینکه به ازای یک کلید، یک خونه برگردونده میشه ولی اون خونه بیش از یک value داره و باید کل آیتم‌هاش رو گشت).
از طرف دیگه برای n داده‌ی ورودی، با احتمال بیش از [tex]1-\frac{1}{n}[/tex] هیچ خونه‌ی هش‌مپ بیش از [tex]\log(n)[/tex] داده (مقدار) نخواهد داشت (که در اصل در این مسأله صرفا [tex]\log(n)[/tex] داده‌ی ورودی داریم، پس خونه‌های هش‌مپ بیش از [tex]\log(\log n)[/tex] مقدار نخواهند داشت که برای درج یا جستجوی n عنصر با ماکزیمم [tex]\log n[/tex] عنصر متفاوت در این سوال ماکزیمم مرتبه‌ی [tex]nlog(\log n)[/tex] خواهیم داشت ولی در کل، مخصوصاً با این تعدادِ کم داده‌ی متمایز مرتبه‌ی درج و جستجوی هش‌مپ رو [tex]O(1)[/tex] میگیرند.
و اما در مورد روش شما، نمیدونم از کجا گفتید لیست مرتب شده داریم. فرض کنید که [tex]\log(n)[/tex] عدد متمایز داریم و تعداد تکرار این اعداد هم بر فرض برابر هستند و به صورت نزولی اومدند، مثلا n=8 و در نتیجه ۳ عدد متمایز داریم. فرض کنید به این صورت اومدند:
۳,۲,۱,۳,۲,۱,۳,۲,۱,۳,۲,۱
الان اینجا هیچ لیست مرتب شده وجود نداره که شما صرفاً ادغام کنید.
(28 بهمن 1395 02:52 ق.ظ)alireza01 نوشته شده توسط: [ -> ]سلام . نظر و جواب دوست عزیزمون Pure Liveliness رو قبول ندارم ، چون در صورت تست گفته شده که مرتب سازی باید مبتنی بر مقایسه باشه ، روش Hash که ایشون استفاده کردن حتی با بهترین تابع ابتکار باز هم ایده مقایسه ای نداره ( این ایده که در مدخل مورد نظر مقدار را افزایش یا وارد کنیم اصلا یک ایده مقایسه ای نیست ، این ایده در اصل همان روش مرتب سازی شمارشی است با یک تفاوت در طول بازه آن و تابع ابتکار ) ، لیست بیشتر الگوریتم هایی که مبتنی بر مقایسه هستند رو بنده استخراج کردم که در جدول زیر میبینید که بهترین زمان متوسط همان [tex]\theta(nlogn)[/tex] است .
روشی که میشه بهش استناد کرد اینه که ما حداکثر [tex]\log n[/tex] عدد متمایز داریم ، یک آرایه دو بعدی کمکی به نام TEMP به همین طول تولید کرده و با مرتبه زمانی [tex]O(n)[/tex] اعداد منحصر به فرد به پیدا کرده و به همراه فرکانس ( تعداد تکرار های آنها ) درون آرایه جدید قرار میدهیم . حال ما [tex]\log n[/tex] عدد داریم ، با هزینه [tex]nlog(\log n)[/tex] آرایه جدید را مرتب میکنیم . سپس بر اساس فرکانس آنها را در آرایه قبلی وارد میکنیم که مرتبه زمانی کلی برابر است با [tex]\theta(nloglogn\: +\: n)\: =\: \theta(nloglogn)[/tex] است .
اگر اشتباه میکنم خوشحال میشم بفرمایید . از پاسخم مطمعن نیستم .
این لزوماً درست نیست که مقایسه‌ای نمیتونه از [tex]\theta(nlogn)[/tex] بهتر باشه وقتی توو صورت سؤال برای توزیع داده‌ها شرط گذاشته. مسائل زیادی وجود داره که مثلا اعداد مسأله در قالب لیست‌های مرتب شده‌ی هم‌اندازه یا غیرهم‌اندازه و ... هستند که بسته به نوع سوال میشه از روش مقایسه‌ای استفاده کرد و مرتبه‌های مختلفی داشت.
ضمناً روش شما دقیقاً همون روش ایشون هست با این تفاوت که صرفاً شما اومدید نحوه‌ی پیاده‌سازی تابع هش‌مپ رو به صورت آرایه درآوردید که در این صورت اندازه‌ی آرایه‌تون باید در ابعاد (رِنج) n باشه که ممکن هست عملی نباشه. ممکن هست شما صرفاً فقط دو عدد متمایز داشته باشید ولی بازه‌ی اون‌ها بزرگ باشه (مثلا یکی ۰ و یکی [tex]10^{12}[/tex]).
البته این حالت کمترین تعداد لیست رو شامل میشه پس nloglonn درواقع کمترین هزینه است البته با این روش.
اینکه فرمودین رنج اعداد مهم نیست و هندل میشه برای من استرسی ایجاد کرد که دوباره باید مبحٍث hash بخونم.
و اینکه گفتید در کل مخصوصا با این تعداد کم داده متمایز مرتبه درج و جستجو ی هش مپ را (1) O میگیرند استرس دیگریست.
ممنون از اطلاعاتتان و اینکه من تاکیدی بر درستی روش خود ندارم فقط منظورم این بود که اولین ایده این روش به ذهن رسید. باز هم ممنون.