ارسال: #۱

۰۷ آبان ۱۳۸۹, ۰۹:۳۳ ب.ظ

saria پرسیده:

مسئله جستجوی تعداد اعداد در محدوده a تا b با پیچیدگی (o(1

الگوریتمی طراحی کنیم که n عدد صحیح مثبت در محدوده ۰ تا k دریافت کنه و در زمان o(1) بررسی کند که تعداد اعداد در محدوده a تا b چقدر میباشد. کدام الگوریتم بهتر است؟
۱/binary
۲/Insertion
۳/counting
۴/radix
(اگه سوال ابتداییه Sorry) لطفا با دلیل و توضیح کامل بگید

ارسال: #۲

۲۷ دى ۱۳۸۹, ۰۹:۱۷ ق.ظ

ف.ش پاسخ داده:

طراحی الگوریتم(o(1))

الگوریتم شمارشی بر اساس فراوانی:
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.

البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.

پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.

ارسال: #۳

۲۷ دى ۱۳۸۹, ۰۹:۴۲ ق.ظ

zr2358 پاسخ داده:

RE: طراحی الگوریتم(o(1))

(۲۷ دى ۱۳۸۹ ۰۹:۱۷ ق.ظ)afagh1389 نوشته شده توسط: الگوریتم شمارشی بر اساس فراوانی:
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.

البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.

پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.

توی این الگوریتمی که دوستان اشاره کردند مقدار هر خونه فراوانی تجمعی آن عدد است (یعنی چندتا عدد قبل از اون عدد وجود داره) نه فراوانی مطلق آن.
اینطوری با منها کردن جواب درست را می گیری.
ولی حالا کلا اساس این الگوریتم Counting فراوانی تجمعی را ذخیره می کنه یا فراوانی مطلق رو؟ Huh

ارسال: #۴

۰۷ آبان ۱۳۸۹, ۰۹:۴۹ ب.ظ

۵۴m4n3h پاسخ داده:

RE: طراحی الگوریتم(o(1))

جواب گزینه‌ی ۳ یعنی counting sort هست فکر کنم!
چون توی الگوریتمش یه آرایه درست میکنه که توی هر خونه از آرایه، فراوانی تجمعیِ اندیسش رو نگه میداره و برای پیدا کردن تعداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!
اما برای بقیه گزینه‌ها مجبورید بشمارید که مرتبه ش n میشه!

ارسال: #۵

۰۸ آبان ۱۳۸۹, ۱۰:۵۶ ق.ظ

jikjik پاسخ داده:

طراحی الگوریتم(o(1))

بله جواب counting هست منم از clrs یاد گرفتم

ارسال: #۶

۰۸ آبان ۱۳۸۹, ۰۲:۰۰ ب.ظ

ف.ش پاسخ داده:

طراحی الگوریتم(o(1))

میدونید این کتاب CLRS در اصل کتابی برای درس طراحی الگوریتم پیشرفته است که جزو یکی از ۳ منبع برای آزمون فراگیر پیام نوره.
در اصل نباید از این کتاب سوال بشه ولی خوب نمیدونم طراحهای سوال چه علاقه ای بهش دارن!!!

ارسال: #۷

۲۵ دى ۱۳۸۹, ۰۴:۳۲ ب.ظ

لهمشد پاسخ داده:

RE: طراحی الگوریتم(o(1))

با سلام:

نقل قول: عداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!

این قسمت اخری که گفتید چه جوری تو O(1) جواب میده فرض کنید
داده های ورودی به این شکل اند .
۱۲و۱۲و۱۵و ۱۵و۱۹و۱۹و۲۳
خب حالا ما یه ارایه داریم که نعداد توش هستش از اندیس ۱۲ تا اندیس ۲۳ به این شکل:
تو اندیس ۱۲ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۲ داریم
تو اندیس ۱۵ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۵داریم
تو اندیس ۱۹ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۹داریم
و تو اندیس ۲۳ عدد ۱ قرار میگیره به معنی که ما فقط یک عدد ۲۳ داریم
خب حالا بخواهیم بدونیم تو رنج ۱۲ تا ۱۹ چند عدد در ورودی است با این گفته شما نمی تونیم از مر تبه O(1) تعداد رو پیدا کنیم ؟؟؟ Exclamation

ارسال: #۸

۲۵ دى ۱۳۸۹, ۰۵:۵۱ ب.ظ

۵۴m4n3h پاسخ داده:

RE: طراحی الگوریتم(o(1))

توی counting sort فراوانی تجمعی عناصر رو نگه میداره!

کد: 

c[12]=2

c[15]=4

c[19]=6

c[23]=7

برای این که بدونیم در بازه‌ی

$12<x\leq 19$ چند تا عدد وجود داره

$c[19]-c[12]=4$ رو حساب می کنیم!

ارسال: #۹

۲۵ دى ۱۳۸۹, ۰۶:۱۲ ب.ظ

لهمشد پاسخ داده:

RE: طراحی الگوریتم(o(1))

چجوری میشه من که متوجه نمی شم چند تا عدد چی تکراری یا غیر تکراری؟؟

ارسال: #۱۰

۲۵ دى ۱۳۸۹, ۱۰:۵۴ ب.ظ

ف.ش پاسخ داده:

طراحی الگوریتم(o(1))

تکراری‌ها حذف نمیشوند وقتی C[2 =4 است یعنی ۴ تا ۲ داریم.

ارسال: #۱۱

۲۷ دى ۱۳۸۹, ۱۰:۰۰ ق.ظ

ف.ش پاسخ داده:

طراحی الگوریتم(o(1))

طبق اون لینکی که گذاشتم فراوانی تجمعی رو ذخیره میکنه!!!

ارسال: #۱۲

۲۷ دى ۱۳۸۹, ۱۰:۱۷ ق.ظ

zr2358 پاسخ داده:

RE: طراحی الگوریتم(o(1))

(۲۷ دى ۱۳۸۹ ۱۰:۰۰ ق.ظ)afagh1389 نوشته شده توسط: طبق اون لینکی که گذاشتم فراوانی تجمعی رو ذخیره میکنه!!!

درسته
اول فراوانی مطلق را میذاره و بعد فراوانی تجمعی هر خونه را حساب میکنه Big Grin

پس مشکلی نیست دیگه منها درست جواب میده Shy

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	تعداد برگ درخت؟؟؟؟؟؟؟	rad.bahar	۴	۵,۳۷۶	۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra
	کمک به حل مسئله	Moha33	۰	۱,۴۵۱	۰۵ تیر ۱۴۰۰ ۰۹:۴۲ ق.ظ آخرین ارسال: Moha33
	دو سوال در مورد درخت BST(درخت جستجوی دودویی)	امیدوار	۳	۵,۹۷۷	۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ آخرین ارسال: marzi.pnh
	زمان جستجوی درخت	fateme.sm	۰	۱,۹۰۰	۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ آخرین ارسال: fateme.sm
	تعداد جواب	mostafaheydar1370	۲۱	۲۰,۸۶۷	۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ آخرین ارسال: miinaa
	در جستجوی اساتید امنیت	wskf	۰	۲,۲۶۵	۱۸ فروردین ۱۳۹۹ ۰۸:۴۶ ب.ظ آخرین ارسال: wskf
	پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت	اsepid8994	۰	۱,۹۳۸	۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994
	تعداد روش های نوشتن عدد n	ss311	۲	۳,۶۳۰	۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311
	تعداد مسیرها در گراف	ss311	۰	۲,۱۵۰	۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311
	تعداد درخت فراگیر	ss311	۰	۲,۴۷۲	۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311

مسئله جستجوی تعداد اعداد در محدوده a تا b با پیچیدگی (o(1

مسئله جستجوی تعداد اعداد در محدوده a تا b با پیچیدگی (o(1

طراحی الگوریتم(o(1))

RE: طراحی الگوریتم(o(1))

RE: طراحی الگوریتم(o(1))

طراحی الگوریتم(o(1))

طراحی الگوریتم(o(1))

RE: طراحی الگوریتم(o(1))

RE: طراحی الگوریتم(o(1))

RE: طراحی الگوریتم(o(1))

طراحی الگوریتم(o(1))

طراحی الگوریتم(o(1))

RE: طراحی الگوریتم(o(1))

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?