الگوریتمی طراحی کنیم که n عدد صحیح مثبت در محدوده ۰ تا k دریافت کنه و در زمان o(1) بررسی کند که تعداد اعداد در محدوده a تا b چقدر میباشد. کدام الگوریتم بهتر است؟
۱/binary
۲/Insertion
۳/counting
۴/radix
(اگه سوال ابتداییه Sorry) لطفا با دلیل و توضیح کامل بگید
جواب گزینه‌ی ۳ یعنی counting sort هست فکر کنم!
چون توی الگوریتمش یه آرایه درست میکنه که توی هر خونه از آرایه، فراوانی تجمعیِ اندیسش رو نگه میداره و برای پیدا کردن تعداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!
اما برای بقیه گزینه‌ها مجبورید بشمارید که مرتبه ش n میشه!
بله جواب counting هست منم از clrs یاد گرفتم
میدونید این کتاب CLRS در اصل کتابی برای درس طراحی الگوریتم پیشرفته است که جزو یکی از ۳ منبع برای آزمون فراگیر پیام نوره.
در اصل نباید از این کتاب سوال بشه ولی خوب نمیدونم طراحهای سوال چه علاقه ای بهش دارن!!!
(۰۸ آبان ۱۳۸۹ ۰۸:۴۹ ق.ظ)javadjj نوشته شده توسط: بصورت کامل توی کتاب سی ال ار اس جلد اول توضیح داده به نظر من خیلی جالبهتو جزوه سید جوادی هم یافت میشود
با سلام:
نقل قول: عداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!این قسمت اخری که گفتید چه جوری تو O(1) جواب میده فرض کنید
داده های ورودی به این شکل اند .
۱۲و۱۲و۱۵و ۱۵و۱۹و۱۹و۲۳
خب حالا ما یه ارایه داریم که نعداد توش هستش از اندیس ۱۲ تا اندیس ۲۳ به این شکل:
تو اندیس ۱۲ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۲ داریم
تو اندیس ۱۵ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۵داریم
تو اندیس ۱۹ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۹داریم
و تو اندیس ۲۳ عدد ۱ قرار میگیره به معنی که ما فقط یک عدد ۲۳ داریم
خب حالا بخواهیم بدونیم تو رنج ۱۲ تا ۱۹ چند عدد در ورودی است با این گفته شما نمی تونیم از مر تبه O(1) تعداد رو پیدا کنیم ؟؟؟
توی counting sort فراوانی تجمعی عناصر رو نگه میداره!
کد:
c[12]=2
c[15]=4
c[19]=6
c[23]=7چجوری میشه من که متوجه نمی شم چند تا عدد چی تکراری یا غیر تکراری؟؟
تکراری‌ها حذف نمیشوند وقتی C[2 =4 است یعنی ۴ تا ۲ داریم.
الگوریتم شمارشی بر اساس فراوانی:
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.
البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.
پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.
(۲۷ دى ۱۳۸۹ ۰۹:۱۷ ق.ظ)afagh1389 نوشته شده توسط: الگوریتم شمارشی بر اساس فراوانی:
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.
البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.
پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.
توی این الگوریتمی که دوستان اشاره کردند مقدار هر خونه فراوانی تجمعی آن عدد است (یعنی چندتا عدد قبل از اون عدد وجود داره) نه فراوانی مطلق آن.
اینطوری با منها کردن جواب درست را می گیری.
ولی حالا کلا اساس این الگوریتم Counting فراوانی تجمعی را ذخیره می کنه یا فراوانی مطلق رو؟
طبق اون لینکی که گذاشتم فراوانی تجمعی رو ذخیره میکنه!!!
(۲۷ دى ۱۳۸۹ ۱۰:۰۰ ق.ظ)afagh1389 نوشته شده توسط: طبق اون لینکی که گذاشتم فراوانی تجمعی رو ذخیره میکنه!!!
درسته
اول فراوانی مطلق را میذاره و بعد فراوانی تجمعی هر خونه را حساب میکنه
پس مشکلی نیست دیگه منها درست جواب میده
