زمان کنونی: ۰۳ دى ۱۴۰۳, ۰۴:۳۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

پیچیدگی زمانی radix

ارسال:
  

g_monireh پرسیده:

پیچیدگی زمانی radix

یه سوال از داشنگاه آزاد بود که نوشته بود بهترین مرتبه زمانی رادیکس میشه o(nlogn) و بدترین میشه O(n2) میخاستم بدونم درسته؟ چطور بهترین میشهnlog n????
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

mahsalove پاسخ داده:

RE: پیچیدگی زمانی radix

(۱۸ بهمن ۱۳۹۲ ۱۲:۲۶ ق.ظ)g_monireh نوشته شده توسط:  یه سوال از داشنگاه آزاد بود که نوشته بود بهترین مرتبه زمانی رادیکس میشه o(nlogn) و بدترین میشه O(n2) میخاستم بدونم درسته؟ چطور بهترین میشهnlog n????

بدترین حالت زمانی است که n/2 عدد یک رقمی و یک عدد n/2 رقمی وجود داشته باشد که در این صورت n/2+1 عدد داریم که تعداد ارقام آنها حداکثر n/2 است و مرتبه تتا
(n/2(n/2+1+10))
(اعداد مبنای ۱۰)یعنی تتا n^2 است.

جالب اینجاست که بهترین زمان این الگوریتم n است نه nlogn مثلا تعداد ارقام ۳ تا باشه عددم در مبنای ۱۰ یا ۲۰ باشه که بخواهیم با radix
sortش کنیم که اونوقت می شه تتا
(۳(n+20))
یعنی تتا n .

احتمالا nlogn میانگین زمانی این الگوریتم بایستی باشه

موفق باشید....
نقل قول این ارسال در یک پاسخ

ارسال:
  

نارین پاسخ داده:

RE: پیچیدگی زمانی radix

(۱۸ بهمن ۱۳۹۲ ۱۲:۴۸ ق.ظ)mahsalove نوشته شده توسط:  
(18 بهمن ۱۳۹۲ ۱۲:۲۶ ق.ظ)g_monireh نوشته شده توسط:  یه سوال از داشنگاه آزاد بود که نوشته بود بهترین مرتبه زمانی رادیکس میشه o(nlogn) و بدترین میشه O(n2) میخاستم بدونم درسته؟ چطور بهترین میشهnlog n????

بدترین حالت زمانی است که n/2 عدد یک رقمی و یک عدد n/2 رقمی وجود داشته باشد که در این صورت n/2+1 عدد داریم که تعداد ارقام آنها حداکثر n/2 است و مرتبه تتا
(n/2(n/2+1+10))
(اعداد مبنای ۱۰)یعنی تتا n^2 است.

جالب اینجاست که بهترین زمان این الگوریتم n است نه nlogn مثلا تعداد ارقام ۳ تا باشه عددم در مبنای ۱۰ یا ۲۰ باشه که بخواهیم با radix
sortش کنیم که اونوقت می شه تتا
(۳(n+20))
یعنی تتا n .

احتمالا nlogn میانگین زمانی این الگوریتم بایستی باشه

موفق باشید....
ولی من توی نوتهام نوشتم بهترین از مرتبه ان اوگ ان الانم کتابمو دادم به کسی این تحلیل شماام به نظر درست میرسه پس اینی که من نوشتم چیه؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

neda_Network پاسخ داده:

RE: پیچیدگی زمانی radix

در این الگوریتم sتعداد ارقام اعداد وnتعداد اعداد موجود در آرایه میباشد اگر تعداد ارقام اعداد یکسان نبود پشت اعدا کوچکتر صفر را در نظر میگیریم بدیهی است که مرتبه اجرایی آن از مرتبهO(n*s)میباشد که در صورتی که s=nمرتبه ی آن برابر باo(n2)و اگر s=lognاز مرتبهo(nlogn)میباشد

پی نوشت:اینا تو کتاب من نوشته Big Grin
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۵,۰۴۴ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۳,۲۷۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۸۲۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۸۱۹ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۸۵۵ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۹۸۱ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  مرتبه زمانی Sanazzz ۰ ۲,۰۶۶ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz
  مشکل در پیچیدگی زمانی ماهی ۲۵۸ ۲ ۳,۰۵۴ ۲۳ تیر ۱۳۹۷ ۱۲:۱۸ ق.ظ
آخرین ارسال: Alisalar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۷,۵۹۷ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  نمودار زمانی مدار میلی! AEM4949 ۱۰ ۱۰,۳۷۹ ۰۹ اسفند ۱۳۹۶ ۰۳:۱۵ ب.ظ
آخرین ارسال: aminfaraji

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

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

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close