عرض سلام و وقت بخیر ...
این سوال تقریبا مشابه یکی از سوال های کتاب ۶۰۰ مساله که یافتن عنصر با تعداد تکرار های بیشتر از [tex]\frac{n}{k}[/tex] در یک آرایه نامرتب هدف آن است میباشد ، برای حل این سوال روش های مختلفی وجود دارد که هر هر کدام دارای مرتبه اجرای مخصوص به خود هستند ، در صورت سوال ذکر شده که فضای مصرفی باید ثابت باشد .
یکی از الگوریتم های حل این سوال که بنده در کتاب Automata and Complexity, Stanford University مشاهده کردم الگوریتم Moore’s Voting است که به اختصار آن را برای شما توضیح میدهم . و برای مطالعه بیشتر به کتاب مراجعه کنید ...
از ابتدای آرایه شروع به حرکت میکنیم ( تعداد تکرار عنصر هدف را پیش فرض ۱ در نظر میگیریم , C=1) و اولین عنصر را میبینیم و فرض میکنیم عنصر هدف همین است ، اندیس را یکی جلو میبریم و با عنصر هدف مقایسه میکنیم اگر برابر بودن که مقدار C را یک واحد افزایش میدهیم و اگر یکی نبود مقدار C را یک واحد کم میکنیم ( اگر C=0 شد عنصر هدف اشتباه انتخاب شده است و عنصر هدف را را به عنصر جاری تغییر میدهیم و مقدار C را به حالت پیش فرض یعنی C=1 تبدیل میکیم ، اگر C صفر نشد کار را دوباره ادامه میدهیم . با اجرای الگوریتم بالا چهره عنصر هدف مشخص میشود و این عنصر همان عنصر مد نظر سوال است مشخص است که مرتبه زمانی این سوال [tex]O(nk )[/tex] است که برای این سوال همان [tex]O(n)[/tex] است و فضای مصرفی ثابت [tex]O(1)[/tex] است یعنی گزینه اول ...
روش دیگری برای حل این سوال استفاده از درهم سازی است که آن هم از مرتبه [tex]O(n)[/tex] است ولی مرتبه فضای مصرفی بیشتر از مقدار ثابت است .

دوست گرامی
از راهنماییتون بسیار سپاسگزارم
شاد و پیروز باشید ان شاالله

(۲۰ فروردین ۱۳۹۶ ۱۰:۵۵ ب.ظ)alireza01 نوشته شده توسط:  عرض سلام و وقت بخیر ...
این سوال تقریبا مشابه یکی از سوال های کتاب ۶۰۰ مساله که یافتن عنصر با تعداد تکرار های بیشتر از [tex]\frac{n}{k}[/tex] در یک آرایه نامرتب هدف آن است میباشد ، برای حل این سوال روش های مختلفی وجود دارد که هر هر کدام دارای مرتبه اجرای مخصوص به خود هستند ، در صورت سوال ذکر شده که فضای مصرفی باید ثابت باشد .
یکی از الگوریتم های حل این سوال که بنده در کتاب Automata and Complexity, Stanford University مشاهده کردم الگوریتم Moore’s Voting است که به اختصار آن را برای شما توضیح میدهم . و برای مطالعه بیشتر به کتاب مراجعه کنید ...
از ابتدای آرایه شروع به حرکت میکنیم ( تعداد تکرار عنصر هدف را پیش فرض ۱ در نظر میگیریم , C=1) و اولین عنصر را میبینیم و فرض میکنیم عنصر هدف همین است ، اندیس را یکی جلو میبریم و با عنصر هدف مقایسه میکنیم اگر برابر بودن که مقدار C را یک واحد افزایش میدهیم و اگر یکی نبود مقدار C را یک واحد کم میکنیم ( اگر C=0 شد عنصر هدف اشتباه انتخاب شده است و عنصر هدف را را به عنصر جاری تغییر میدهیم و مقدار C را به حالت پیش فرض یعنی C=1 تبدیل میکیم ، اگر C صفر نشد کار را دوباره ادامه میدهیم . با اجرای الگوریتم بالا چهره عنصر هدف مشخص میشود و این عنصر همان عنصر مد نظر سوال است مشخص است که مرتبه زمانی این سوال [tex]O(nk )[/tex] است که برای این سوال همان [tex]O(n)[/tex] است و فضای مصرفی ثابت [tex]O(1)[/tex] است یعنی گزینه اول ...
روش دیگری برای حل این سوال استفاده از درهم سازی است که آن هم از مرتبه [tex]O(n)[/tex] است ولی مرتبه فضای مصرفی بیشتر از مقدار ثابت است .

سلام دوست گرامی
به نظر می رسد این روش فقط برای یافتن عنصر اکثریت(منظور عنصری با تکرار بیش از [tex]\frac{n}{2}[/tex]) است وبرای مقادیر بیشتر از ۲ برای k احتمالا تعداد شمارنده ها را باید بیشتر کنیم تابه مرتبه[tex]O(kn)[/tex] برسیم البته در این حالت هم مقدار فضا [tex]O(k)[/tex] میشه .اگر غیر این است لطفا با یک مثال توضیح دهید.(فکر کنم در این روش هم تعداد اعداد داخل ارایه هم باید k باشد.)
نظر تون در باره این روش حل چیه؟ که
[tex]\frac{n}{3}[/tex] مین و [tex]\frac{2n}{3}[/tex] مین min را یافته و تحت انها افراز کرده حالا عنصر هدف یکی از این دو یا هر دو است کافیه با یک بار پیمایش ارایه تعداد هر دو را با دو شمارنده بشماریم .اگر تعداد بیشتر از [tex]\frac{n}{3}[/tex] باشد کار تمام است وگرنه وجود ندارد.
نظر تون درباره این ابهام چیه؟ که
احتمال داره ارایه دو تا عنصر با تکرار بیش از [tex]\frac{n}{3}[/tex] داشته باشه.کدام باید انتخاب شود.

(۲۱ فروردین ۱۳۹۶ ۰۵:۳۳ ب.ظ)msour44 نوشته شده توسط:  سلام دوست گرامی
به نظر می رسد این روش فقط برای یافتن عنصر اکثریت(منظور عنصری با تکرار بیش از [tex]\frac{n}{2}[/tex]) است وبرای مقادیر بیشتر از ۲ برای k احتمالا تعداد شمارنده ها را باید بیشتر کنیم تابه مرتبه[tex]O(kn)[/tex] برسیم البته در این حالت هم مقدار فضا [tex]O(k)[/tex] میشه .اگر غیر این است لطفا با یک مثال توضیح دهید.(فکر کنم در این روش هم تعداد اعداد داخل ارایه هم باید k باشد.)
نظر تون در باره این روش حل چیه؟ که
[tex]\frac{n}{3}[/tex] مین و [tex]\frac{2n}{3}[/tex] مین min را یافته و تحت انها افراز کرده حالا عنصر هدف یکی از این دو یا هر دو است کافیه با یک بار پیمایش ارایه تعداد هر دو را با دو شمارنده بشماریم .اگر تعداد بیشتر از [tex]\frac{n}{3}[/tex] باشد کار تمام است وگرنه وجود ندارد.
نظر تون درباره این ابهام چیه؟ که
احتمال داره ارایه دو تا عنصر با تکرار بیش از [tex]\frac{n}{3}[/tex] داشته باشه.کدام باید انتخاب شود.

سلام و خسته نباشید ...
ابتدا سوالاتی که برایتان پیش آمده را بررسی میکنیم و بعد به سراغ الگوریتم شما میرویم ..
این جمله که اگر تعداد عناصر با تکرار های بیش از [tex]\frac{n}{k}[/tex] بیش از یکی باشد یک ابهام برای این الگوریتم است ، درسته اما من فقط خواستم الگوریتمی کوتاه اراعه بدم که مفهوم اکثریت رو داشته باشه و قابل فهم باشه وگر نا حرف شما درسته . اما در کتاب الگوریتمی ذکر شده که میتوان هر تعداد عنصر با شرط فوق را به کمک [tex]Struct[/tex] و ساخت آرایه از ساختمان برای هر عنصر پیدا کرد ، اما روش ساده تر همان در هم سازی با تابع درهم ساز مناسب ( هندلینگ اعداد منفی و طول مناسب ) است که ، طول جدول را [tex]k[/tex] میگیریم ( در ابتدا با مقادیر ۰ ) و شروع به گذر از آرایه میکنیم ، اگر به عنصر جدیدی رسیدیم کم طول ترین مدخل را در یک آرایه کمکی ذخیره میکنیم که بعدا در صورت نیاز به آن مراجعه کنیم . طول آرایه کمکی هم مشخصه که از مرتبه [tex]O(k)[/tex] است ، در نهایت میتوان مقدار خانه هایی که عنصر آنها عدد بیشتر از [tex]\frac{n}{k}[/tex] را به خروجی برد ، اگر کمی دقت کنیم مرتبه زمانی این کد همان [tex]O(nk)[/tex] خواهد شد . و فضای مصرفی هم همان طور که شما گفتید [tex]O(k)[/tex] خواهد شد . دقت کنید که طول آرایه تاثیری رو روند حل مساله ندارد و نمیتوان طول آن را محدود به [tex]k[/tex] کرد .
در مورد الگوریتم شما هم فکر نمیکنم خروجی غلطی بدهد و ایده جالبی است ( جای کار داره ) فقط مشکلش اینه که فقط یکی از هدف ها رو پیدا میکنه.
اگر نظری دارید خوشحال میشوم استفاده کنم .

(۲۱ فروردین ۱۳۹۶ ۰۶:۳۱ ب.ظ)alireza01 نوشته شده توسط:  

(21 فروردین ۱۳۹۶ ۰۵:۳۳ ب.ظ)msour44 نوشته شده توسط:  سلام دوست گرامی
به نظر می رسد این روش فقط برای یافتن عنصر اکثریت(منظور عنصری با تکرار بیش از [tex]\frac{n}{2}[/tex]) است وبرای مقادیر بیشتر از ۲ برای k احتمالا تعداد شمارنده ها را باید بیشتر کنیم تابه مرتبه[tex]O(kn)[/tex] برسیم البته در این حالت هم مقدار فضا [tex]O(k)[/tex] میشه .اگر غیر این است لطفا با یک مثال توضیح دهید.(فکر کنم در این روش هم تعداد اعداد داخل ارایه هم باید k باشد.)
نظر تون در باره این روش حل چیه؟ که
[tex]\frac{n}{3}[/tex] مین و [tex]\frac{2n}{3}[/tex] مین min را یافته و تحت انها افراز کرده حالا عنصر هدف یکی از این دو یا هر دو است کافیه با یک بار پیمایش ارایه تعداد هر دو را با دو شمارنده بشماریم .اگر تعداد بیشتر از [tex]\frac{n}{3}[/tex] باشد کار تمام است وگرنه وجود ندارد.
نظر تون درباره این ابهام چیه؟ که
احتمال داره ارایه دو تا عنصر با تکرار بیش از [tex]\frac{n}{3}[/tex] داشته باشه.کدام باید انتخاب شود.

سلام و خسته نباشید ...
ابتدا سوالاتی که برایتان پیش آمده را بررسی میکنیم و بعد به سراغ الگوریتم شما میرویم ..
این جمله که اگر تعداد عناصر با تکرار های بیش از [tex]\frac{n}{k}[/tex] بیش از یکی باشد یک ابهام برای این الگوریتم است ، درسته اما من فقط خواستم الگوریتمی کوتاه اراعه بدم که مفهوم اکثریت رو داشته باشه و قابل فهم باشه وگر نا حرف شما درسته . اما در کتاب الگوریتمی ذکر شده که میتوان هر تعداد عنصر با شرط فوق را به کمک [tex]Struct[/tex] و ساخت آرایه از ساختمان برای هر عنصر پیدا کرد ، اما روش ساده تر همان در هم سازی با تابع درهم ساز مناسب ( هندلینگ اعداد منفی و طول مناسب ) است که ، طول جدول را [tex]k[/tex] میگیریم ( در ابتدا با مقادیر ۰ ) و شروع به گذر از آرایه میکنیم ، اگر به عنصر جدیدی رسیدیم کم طول ترین مدخل را در یک آرایه کمکی ذخیره میکنیم که بعدا در صورت نیاز به آن مراجعه کنیم . طول آرایه کمکی هم مشخصه که از مرتبه [tex]O(k)[/tex] است ، در نهایت میتوان مقدار خانه هایی که عنصر آنها عدد بیشتر از [tex]\frac{n}{k}[/tex] را به خروجی برد ، اگر کمی دقت کنیم مرتبه زمانی این کد همان [tex]O(nk)[/tex] خواهد شد . و فضای مصرفی هم همان طور که شما گفتید [tex]O(k)[/tex] خواهد شد . دقت کنید که طول آرایه تاثیری رو روند حل مساله ندارد و نمیتوان طول آن را محدود به [tex]k[/tex] کرد .
در مورد الگوریتم شما هم فکر نمیکنم خروجی غلطی بدهد و ایده جالبی است ( جای کار داره ) فقط مشکلش اینه که فقط یکی از هدف ها رو پیدا میکنه.
اگر نظری دارید خوشحال میشوم استفاده کنم .

سلام
فقط اینو بگم که عرض کردم از دو شمارنده استفاده میشه و بعد یک بار ارایه پیمایش و تعداد عنصر های هدف شمارش می شود([tex]\frac{n}{3}[/tex] مین و [tex]\frac{2n}{3}[/tex] مین min که اگر تعداد هر دو بیشتر از [tex]\frac{n}{3}[/tex] باشه هر دو را برمی گردوکافی از دو تا if استفاده کنیم ممکن است این دو عدد اصلا یکسان باشند)
در واقع چون از تست های ارشد بود احتمال دادم با مباحثی که در سطح کارشناسی مطرح می شود راه حلی برای ان وجود دارد
اما در یاداشت هام یک نکته نوشتم که گفتم شاید به درد دوستان بیاید
برای یک k داده شده([tex]2\le k\le n[/tex]) هر الگوریتم بر مبنای مقایسه روی عناصر ارایه برای پیدا کردن عناصری که بیش از [tex]\frac{n}{k}[/tex] تکرار شده اندحداقل به [tex]O(n\: \ast\: \lg k)[/tex] مقایسه نیاز دارد با پیچیدگی فضایی [tex]O(K)[/tex]
درباره اثبات چیزی یادم نمیاد ولی میدونم از درخت AVL استفاده کرده بود.

(۲۱ فروردین ۱۳۹۶ ۰۸:۱۴ ب.ظ)msour44 نوشته شده توسط:  سلام
فقط اینو بگم که عرض کردم از دو شمارنده استفاده میشه و بعد یک بار ارایه پیمایش و تعداد عنصر های هدف شمارش می شود([tex]\frac{n}{3}[/tex] مین و [tex]\frac{2n}{3}[/tex] مین min که اگر تعداد هر دو بیشتر از [tex]\frac{n}{3}[/tex] باشه هر دو را برمی گردوکافی از دو تا if استفاده کنیم ممکن است این دو عدد اصلا یکسان باشند)
در واقع چون از تست های ارشد بود احتمال دادم با مباحثی که در سطح کارشناسی مطرح می شود راه حلی برای ان وجود دارد
اما در یاداشت هام یک نکته نوشتم که گفتم شاید به درد دوستان بیاید
برای یک k داده شده([tex]2\le k\le n[/tex]) هر الگوریتم بر مبنای مقایسه روی عناصر ارایه برای پیدا کردن عناصری که بیش از [tex]\frac{n}{k}[/tex] تکرار شده اندحداقل به [tex]O(n\: \ast\: \lg k)[/tex] مقایسه نیاز دارد با پیچیدگی فضایی [tex]O(K)[/tex]
درباره اثبات چیزی یادم نمیاد ولی میدونم از درخت AVL استفاده کرده بود.

از شما بابت این نکات ممنونم و حتما به دوستان هم پیشنهاد میکنم استفاده کنن .
حالا که نکته شما را دیدم که تعداد حداقل تعداد مقایسه ها [tex]nlogk[/tex] بود یادم اومد که مدتی پیش الگوریتمی دیدم که برای ارقام بزرگ [tex]K[/tex] این مساله را در زمان [tex]O(nlogk)[/tex] حل میکرد . البته اثبات شو نمیدونم و جایی هم ندیدم فک کنم یکی از تمرینات کتابی که تو پست اول عرض کردم باشه .... ( بد نیست اینم بدونید ... )

(۲۱ فروردین ۱۳۹۶ ۰۸:۳۶ ب.ظ)alireza01 نوشته شده توسط:  

(21 فروردین ۱۳۹۶ ۰۸:۱۴ ب.ظ)msour44 نوشته شده توسط:  سلام
فقط اینو بگم که عرض کردم از دو شمارنده استفاده میشه و بعد یک بار ارایه پیمایش و تعداد عنصر های هدف شمارش می شود([tex]\frac{n}{3}[/tex] مین و [tex]\frac{2n}{3}[/tex] مین min که اگر تعداد هر دو بیشتر از [tex]\frac{n}{3}[/tex] باشه هر دو را برمی گردوکافی از دو تا if استفاده کنیم ممکن است این دو عدد اصلا یکسان باشند)
در واقع چون از تست های ارشد بود احتمال دادم با مباحثی که در سطح کارشناسی مطرح می شود راه حلی برای ان وجود دارد
اما در یاداشت هام یک نکته نوشتم که گفتم شاید به درد دوستان بیاید
برای یک k داده شده([tex]2\le k\le n[/tex]) هر الگوریتم بر مبنای مقایسه روی عناصر ارایه برای پیدا کردن عناصری که بیش از [tex]\frac{n}{k}[/tex] تکرار شده اندحداقل به [tex]O(n\: \ast\: \lg k)[/tex] مقایسه نیاز دارد با پیچیدگی فضایی [tex]O(K)[/tex]
درباره اثبات چیزی یادم نمیاد ولی میدونم از درخت AVL استفاده کرده بود.

از شما بابت این نکات ممنونم و حتما به دوستان هم پیشنهاد میکنم استفاده کنن .
حالا که نکته شما را دیدم که تعداد حداقل تعداد مقایسه ها [tex]nlogk[/tex] بود یادم اومد که مدتی پیش الگوریتمی دیدم که برای ارقام بزرگ [tex]K[/tex] این مساله را در زمان [tex]O(nlogk)[/tex] حل میکرد . البته اثبات شو نمیدونم و جایی هم ندیدم فک کنم یکی از تمرینات کتابی که تو پست اول عرض کردم باشه .... ( بد نیست اینم بدونید ... )

دلم نمیاد این موضوع را عنوان نکنم که در این مبحث اگر k ثابت نباشد مثلا اگر lgn باشد با زمان [tex]O(n\: \lg\lg n)[/tex] می توان به جواب رسید.!!! این مرتبه منو یاد یکی از تمرینات قدسی میندازه که اتفاقا یکی از بچه ها هم اونو چند وقت پیش مطرح کرده بود مبنی بر اینکه
می توان n عدد مجزا از هم را که بین ۱ تا [tex]n^{\lg n}[/tex] هستند در [tex]O(n\: \lg\lg n)[/tex] مرتب کرد. در واقع اگر ارایه ورودی این وِیژگی لازم را داشته باشد(۱ تا ...) می توانیم برای یافتن عنصر مورد نظر از مرتب سازی استفاده کنیم .مزیت کدام بهتر است. محدویت های حافظه هم جای خود را دارد.
به هر حال موضوع جالبی است و نیازمند تلاش و تحقیق بیشتر
من هم از شما سپاسگزارم.