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

ممنون .

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

(27 بهمن ۱۳۹۵ ۰۲:۵۰ ب.ظ)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] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش می‌کنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.

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

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

(27 بهمن ۱۳۹۵ ۰۲:۵۰ ب.ظ)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] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش می‌کنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.

ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟
تقریبا شبیه روش مرتب سازی شمارشی نیست؟

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

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

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

(27 بهمن ۱۳۹۵ ۰۲:۵۰ ب.ظ)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] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش می‌کنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.

ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟
تقریبا شبیه روش مرتب سازی شمارشی نیست؟

به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب می‌کنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\log(n))[/tex] در حالی که در مرتب‌سازی شمارشی همون [tex]\theta(n)[/tex] می‌شد.

(۲۷ بهمن ۱۳۹۵ ۱۱:۴۴ ب.ظ)msour44 نوشته شده توسط:  ممنون از پاسختان
چرا در hash تعداد مدخل ها رو لگاریت n میگیرد نباید به اندازه بزرگترین عدد موجود در ارایه باشه که ممکنه نسبت به n نمایی باشه؟منظورم اینکه اندیس ها نباید اعداد متوالی باشه ؟درست n عدد داریم با ضریب تکرار لگاریتمی ولی اگه از Hashاستفاده کنیم برای ذخیره تعداد تکرار هر عدد نباید اندیس رو عدد و درایه ان را تعداد تکرار تصور کنیم منظورت چیز دیگری است؟
ببخشید که وقت تونو میگیرم ولی اگه اشتباه نکنم این تست سال ۸۹ نرم افزاره که هادی یوسفی جوابشو گزینه ۳ گفته به این صورت که با nعدد داده شده یک BST متوازن می سازیم ولی در هر نود تعداد تکرار ان را ذخیره می کنیم که ارتفاع این درخت loglogn میشه و مرتبه ساخت n.loglogn سپس درخت را به صورت میان ترتیب پیمایش میکنیم که مرتبه کل میشه n.loglogn مدرسان هم همین گزینه رو گفته با همین استدلال تقریبا مشابه با هادی یوسفی.
ولی روشی که من این تست و اولین بار جواب دادم این بود که می توان از متن سوال پی برد که logn لیست مرتب شده با توجه به تکرار هر عدد در بدترین حالت داریم و اینکه مرتبه ادغام kلیست مرتب در حداقل n.logk است پس مرتبه کل میشه n.loglogn
موفق باشید

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

(27 بهمن ۱۳۹۵ ۱۰:۰۸ ب.ظ)Behnam‌ نوشته شده توسط:  

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

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

(27 بهمن ۱۳۹۵ ۰۲:۵۰ ب.ظ)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] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش می‌کنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.

ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟
تقریبا شبیه روش مرتب سازی شمارشی نیست؟

به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب می‌کنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\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
موفق باشید

(۲۸ بهمن ۱۳۹۵ ۰۲:۵۲ ق.ظ)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] است .

اگر اشتباه میکنم خوشحال میشم بفرمایید . از پاسخم مطمعن نیستم .

(۲۸ بهمن ۱۳۹۵ ۰۳:۳۰ ق.ظ)alireza01 نوشته شده توسط:  ممنون از وقت گذاشتن و پاسخگویی تون ، نمیدونم چرا پستم پاک شد.

(۲۸ بهمن ۱۳۹۵ ۰۳:۳۰ ق.ظ)alireza01 نوشته شده توسط:  ممنون از وقت گذاشتن و پاسخگویی تون ، نمیدونم چرا پستم پاک شد.

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

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

(27 بهمن ۱۳۹۵ ۱۰:۰۸ ب.ظ)Behnam‌ نوشته شده توسط:  

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

(27 بهمن ۱۳۹۵ ۰۹:۰۹ ب.ظ)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] کمتر است، می‌توان از این مرحله چشمپوشی کرد.
در نهایت روی این لیست مرتب شده پیمایش می‌کنیم و برای هر عدد، به تعدادِ آن عدد (که قبلاً در مپ نگه داشتیم) می‌نویسیم.

ببخشید این روشی که شما گفتید مقایسه ای محسوب میشه؟
تقریبا شبیه روش مرتب سازی شمارشی نیست؟

به نظرم فرق دارند چون اولاً در مرتب‌سازی شمارشی، طول بازه باید محدود باشد در حالی که در اینجا محدودیتی وجود ندارد. همچنین در مرتب‌سازی شمارشی، هیچ مقایسه‌ای صورت نمی‌گیرد در حالی که در اینجا، لیستِ بدست آمده از hashmap رو با یک روش مقایسه‌ای (مثل merge sort) مرتب می‌کنیم. اگر تنوع اعداد به جای [tex]\log(n)[/tex] مثلاً [tex]\frac{n}{100}[/tex] بود، پیچیدگی روش گفته شده میشد [tex]\theta(n\cdot\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 و در نتیجه ۳ عدد متمایز داریم. فرض کنید به این صورت اومدند:
۳,۲,۱,۳,۲,۱,۳,۲,۱,۳,۲,۱
الان اینجا هیچ لیست مرتب شده وجود نداره که شما صرفاً ادغام کنید.

---

(۲۸ بهمن ۱۳۹۵ ۰۲:۵۲ ق.ظ)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]).