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

مرتبه زمانی ساخت درخت از پیمایش

ارسال:
  

matinpf پرسیده:

مرتبه زمانی ساخت درخت از پیمایش

سلام

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

۰
ارسال:
  

BBumir پاسخ داده:

RE: مرتبه زمانی ساخت درخت از پیمایش

(۰۱ مرداد ۱۳۹۶ ۱۱:۱۸ ق.ظ)matinpf نوشته شده توسط:  سلام

دوستان , اگر ما پیشمایش میان ترتیب و پیش ترتیب رو داشته باشیم , مرتبه زمانی ساخت درخت از چه مرتبه ای میشه ؟

سلام؛
مرتبه‌اش از مرتبه‌ی تعداد گره‌های درخت ورودیه.
از حاصل پیمایش پیش‌ترتیب، گره ریشه برای مرحله‌ی جاری انتخاب می‌شه. این عنصر آرایه حاصل از پیمایش میان‌ترتیب رو به دو زیر مسأله تقسیم می‌کنه. که برای اونا هم همین‌کار رو انجام می‌دیم تا ریشه‌های سطح بعد پیدا بشه. یه جورایی می‌شه زمان اجرای این کار رو این شکلی توصیف کرد:
[tex]T(n)\: =\: T(n-m)+T(m-۱)+O(۱)[/tex]

تعداد مراحل پیدا کردن ریشه (که خودش از مرتبه‌ی [tex]O(۱)[/tex]) برابر تعداد گره‌های درخته بنابراین مرتبه اجرا از مرتبه‌ی تعداد گره‌های درخت ورودیه.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۴۰ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۱ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۲ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۲ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۳ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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