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