۰
subtitle
ارسال: #۱
مسئله جستجوی تعداد اعداد در محدوده a تا b با پیچیدگی (o(1
الگوریتمی طراحی کنیم که n عدد صحیح مثبت در محدوده ۰ تا k دریافت کنه و در زمان o(1) بررسی کند که تعداد اعداد در محدوده a تا b چقدر میباشد. کدام الگوریتم بهتر است؟
۱/binary
۲/Insertion
۳/counting
۴/radix
(اگه سوال ابتداییه Sorry) لطفا با دلیل و توضیح کامل بگید
۱/binary
۲/Insertion
۳/counting
۴/radix
(اگه سوال ابتداییه Sorry) لطفا با دلیل و توضیح کامل بگید
۰
ارسال: #۲
طراحی الگوریتم(o(1))
الگوریتم شمارشی بر اساس فراوانی:
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.
البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.
پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.
البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.
پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.
ارسال: #۳
RE: طراحی الگوریتم(o(1))
(۲۷ دى ۱۳۸۹ ۰۹:۱۷ ق.ظ)afagh1389 نوشته شده توسط: الگوریتم شمارشی بر اساس فراوانی:
مثلا اگه آرایه ۱۰ عضوی باشه (۱۰ تا خونه داشته باشه) ما هم یه لیست از اعداد داریم که میخواهیم مرتب کنیم این اعداد باید توی بازه ۰ تا ۹ باشند تا بتونیم نظیر به نظیر توی خونه های آرایه بگذاریمشون یعنی هر عدد میره توی خونه خودش مثلا اگه ۳ داریم میره توی خونه ۳ و .... اگه دوبار ۳ داشته باشیم در خانه ۳ ،۲ قرار میگیره یعنی هر i که دیدیم یک واحد به A[i (که در ابتدا صفره) اضافه میکنیم (شبیه چوب خط)و وقتی میخواهیم لیست مرتب رو چاپ کنیم از خونه صفر شروع میکنیم و وقتی توی خونه i هستیم به تعداد A[i( محتویات اون خونه) i رو پشت سر هم چاپ میکنیم.
البته میتونیم وقتی فراوانی‌ها رو بدست آوردیم فراوانی تجمعی هر خونه رو بدست بیاریم.اگه به سایت زیر مراجعه کنید دقیقا مراحل رو توضیح داده.(هر بار که روی step کلیک کنید یه مرحله از مرتب سازی رو بهتون نشون میده )
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این روش جستجو جامع نیست چون فقط وقتی جواب میده که اعداد توی بازه مشخصی باشند و وقتی بازه بزرگ باشه حافظه زیادی میگیره.
پیچیدگی این مرتب سازی O(n ولی چون جامع نیست نمیتونیم بگیم که ما مرتب سازی با این پیچیدگی داریم و مرتب سازی های جامع از O(nlogn هستند.
توی این الگوریتمی که دوستان اشاره کردند مقدار هر خونه فراوانی تجمعی آن عدد است (یعنی چندتا عدد قبل از اون عدد وجود داره) نه فراوانی مطلق آن.
اینطوری با منها کردن جواب درست را می گیری.
ولی حالا کلا اساس این الگوریتم Counting فراوانی تجمعی را ذخیره می کنه یا فراوانی مطلق رو؟
۰
ارسال: #۴
RE: طراحی الگوریتم(o(1))
جواب گزینه‌ی ۳ یعنی counting sort هست فکر کنم!
چون توی الگوریتمش یه آرایه درست میکنه که توی هر خونه از آرایه، فراوانی تجمعیِ اندیسش رو نگه میداره و برای پیدا کردن تعداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!
اما برای بقیه گزینه‌ها مجبورید بشمارید که مرتبه ش n میشه!
چون توی الگوریتمش یه آرایه درست میکنه که توی هر خونه از آرایه، فراوانی تجمعیِ اندیسش رو نگه میداره و برای پیدا کردن تعداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!
اما برای بقیه گزینه‌ها مجبورید بشمارید که مرتبه ش n میشه!
۰
۰
ارسال: #۶
طراحی الگوریتم(o(1))
میدونید این کتاب CLRS در اصل کتابی برای درس طراحی الگوریتم پیشرفته است که جزو یکی از ۳ منبع برای آزمون فراگیر پیام نوره.
در اصل نباید از این کتاب سوال بشه ولی خوب نمیدونم طراحهای سوال چه علاقه ای بهش دارن!!!
در اصل نباید از این کتاب سوال بشه ولی خوب نمیدونم طراحهای سوال چه علاقه ای بهش دارن!!!
۰
ارسال: #۷
RE: طراحی الگوریتم(o(1))
با سلام:
داده های ورودی به این شکل اند .
۱۲و۱۲و۱۵و ۱۵و۱۹و۱۹و۲۳
خب حالا ما یه ارایه داریم که نعداد توش هستش از اندیس ۱۲ تا اندیس ۲۳ به این شکل:
تو اندیس ۱۲ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۲ داریم
تو اندیس ۱۵ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۵داریم
تو اندیس ۱۹ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۹داریم
و تو اندیس ۲۳ عدد ۱ قرار میگیره به معنی که ما فقط یک عدد ۲۳ داریم
خب حالا بخواهیم بدونیم تو رنج ۱۲ تا ۱۹ چند عدد در ورودی است با این گفته شما نمی تونیم از مر تبه O(1) تعداد رو پیدا کنیم ؟؟؟
نقل قول: عداد اعداد در بازه‌ی a تا b فقط کافیه مقدار خونه‌ی a رو از مقدار خونه‌ی b کم کنیم یعنی توی (O(1 جواب میده!این قسمت اخری که گفتید چه جوری تو O(1) جواب میده فرض کنید
داده های ورودی به این شکل اند .
۱۲و۱۲و۱۵و ۱۵و۱۹و۱۹و۲۳
خب حالا ما یه ارایه داریم که نعداد توش هستش از اندیس ۱۲ تا اندیس ۲۳ به این شکل:
تو اندیس ۱۲ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۲ داریم
تو اندیس ۱۵ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۵داریم
تو اندیس ۱۹ عدد ۲ قرار می گیره به این معنی که ما تعداد ۲ تا عدد ۱۹داریم
و تو اندیس ۲۳ عدد ۱ قرار میگیره به معنی که ما فقط یک عدد ۲۳ داریم
خب حالا بخواهیم بدونیم تو رنج ۱۲ تا ۱۹ چند عدد در ورودی است با این گفته شما نمی تونیم از مر تبه O(1) تعداد رو پیدا کنیم ؟؟؟
۰
ارسال: #۸
RE: طراحی الگوریتم(o(1))
توی counting sort فراوانی تجمعی عناصر رو نگه میداره!
برای این که بدونیم در بازه‌ی [tex]12<x\leq 19[/tex] چند تا عدد وجود داره [tex]c[19]-c[12]=4[/tex] رو حساب می کنیم!
کد:
c[12]=2
c[15]=4
c[19]=6
c[23]=7
۰
ارسال: #۹
RE: طراحی الگوریتم(o(1))
چجوری میشه من که متوجه نمی شم چند تا عدد چی تکراری یا غیر تکراری؟؟
۰
۰
ارسال: #۱۲
RE: طراحی الگوریتم(o(1))
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| تعداد برگ درخت؟؟؟؟؟؟؟ | 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 |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close