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

مرتبه زمانی ساخت یک صف اولویت؟

ارسال:
  

NarimanN2 پرسیده:

مرتبه زمانی ساخت یک صف اولویت؟

سلام
می دونم که زمان ساخت یک صف اولویت از O(nlogn) هست اما چند جا دیدم که اون رو از مرتبه O(n) در نظر گرفتن. ممکنه یکی بهم توضیح بده که بالاخره کدوم درسته؟
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

MShariati پاسخ داده:

RE: مرتبه زمانی ساخت یک صف اولویت؟

تو CLRS کاملاً روی این موضوع بحث شده. اجمالاً، ما از برگ‌ها (یعنی نیمه‌ی آخر آرایه) شروع می‌کنیم و حداکثر روی n/2 عنصر عمل Heapify که در حالت کلی (logn)O به حساب میاد رو انجام میدیم. اما نکته اینجاست که این برگ‌ها در اجدادشان با هم همپوشانی دارند و برآیند عملیات انجام گرفته توسط همه‌ی این Heapifyها بیش از (n)O نمیشه (برای اثباتش به کتاب مراجعه کنید).
امیدوارم اشتباه نکرده باشم، چون مدت‌ها پیش خوندمش.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

MisTeR پاسخ داده:

RE: مرتبه زمانی ساخت یک صف اولویت؟

(۲۶ فروردین ۱۳۹۵ ۱۲:۴۳ ب.ظ)NarimanN2 نوشته شده توسط:  سلام
می دونم که زمان ساخت یک صف اولویت از O(nlogn) هست اما چند جا دیدم که اون رو از مرتبه O(n) در نظر گرفتن. ممکنه یکی بهم توضیح بده که بالاخره کدوم درسته؟
چیزی که در کتاب داده ساختار دکتر قدسی نوشته اینه برای صف اولویت گفته همون هرم است بعدش برای هزینه تبدیل یک آرایه n عضوی به هرم بیشینه [tex]\langle n\rangle O[/tex] حساب کرده نه [tex]\langle nlogn\rangle O[/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

mahmood19227 پاسخ داده:

RE: مرتبه زمانی ساخت یک صف اولویت؟

تا اونجایی که من میدونم بحث صف لولویت و هیپ از هم جدتست
صف اولویت رو در حالت کلی سه جور میشه ساخت
۱- لیست مرتب با مرتبه n به توان ۲
۲- لییت نا مرتب با مرتبه n
۳- هیپ با مرتبه nlogn

Sent from my HTC One_E8 dual sim using Tapatalk
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۹۴۵ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  دانشگاه های پزشکی رو برای رشته انفورماتیک چطوری اولویت بندی کنم ؟ mrpool ۷ ۹,۱۱۰ ۲۴ فروردین ۱۴۰۰ ۰۱:۵۲ ق.ظ
آخرین ارسال: hossein1991
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۹۵ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۵۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۳,۰۷۵ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۶۷۳ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۷۹۵ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۸۲۱ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۳,۷۳۳ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  فرآیند ساخت درب ریلی mohii12 ۰ ۱,۹۳۷ ۲۷ اسفند ۱۳۹۷ ۰۴:۴۸ ب.ظ
آخرین ارسال: mohii12

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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