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

دو سوال در مورد درخت BST(درخت جستجوی دودویی)

ارسال:
۱۷ شهریور ۱۳۹۶, ۰۱:۰۳ ب.ظ
دو سوال در مورد درخت BST(درخت جستجوی دودویی)
با سلام و احترام
دوستان خواهشا اطلاعاتی دارند ارائه بدن، ممنون میشم :
سوال ۱ - بهترین زمان ممکن برای محاسبه ارتفاع درخت BST؟ الف - (h)O ب- (n)O ج - (lgn)O د - ج - (nlgn)O

سوال ۲ - بهترین زمان ممکن برای تشخیص متوازن بودن یا نبودن دودویی(نه BST)؟ همون گزینه های سوال اول. h : یعنی ارتفاع درخت

با تشکر
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۰۱ آبان ۱۳۹۶, ۰۹:۲۱ ب.ظ
RE: دو سوال در مورد درخت BST(درخت جستجوی دودویی)
(۰۴ مهر ۱۳۹۶ ۱۰:۳۹ ب.ظ)omidelf نوشته شده توسط:  
(17 شهریور ۱۳۹۶ ۰۱:۰۳ ب.ظ)امیدوار نوشته شده توسط:  با سلام و احترام
دوستان خواهشا اطلاعاتی دارند ارائه بدن، ممنون میشم :
سوال ۱ - بهترین زمان ممکن برای محاسبه ارتفاع درخت BST؟ الف - (h)O ب- (n)O ج - (lgn)O د - ج - (nlgn)O

سوال ۲ - بهترین زمان ممکن برای تشخیص متوازن بودن یا نبودن دودویی(نه BST)؟ همون گزینه های سوال اول. h : یعنی ارتفاع درخت

با تشکر

سلام

سوال ۱ :

بهترین زمان وقتی میشه که موقع طی کردن مسیر از بالا به پایین همه مسیر هارو درست انتخاب کنه پس میشه ارتفاع درخت یا همون
(O(logn

سوال ۲ :

میشه (O(n با توجه به این لینک :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

با تشکر از پاسخ شما
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: marzi.pnh
ارسال:
۰۷ مهر ۱۳۹۸, ۰۶:۴۵ ب.ظ
RE: دو سوال در مورد درخت BST(درخت جستجوی دودویی)
با سلام
لطفا به دو سوال بنده جواب دهید

۱-بهترین زمان ممکن که می توان با n ;کلید یک درخت جستجوی دودویی با ارتفاع دقیقا برابر n-1 ایجاد نمود کدام است؟

log n n n^2 nlog n


۲-پیچیدگی محاسباتی یافتن تعداد مولفه های همبندی یک گراف اسپارس با n نود و m یال

nm n+m m nlogn+m

سپاس فراوان
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۰ دى ۱۳۹۹, ۱۲:۰۴ ق.ظ (آخرین ویرایش در این ارسال: ۱۰ دى ۱۳۹۹ ۱۲:۰۸ ق.ظ، توسط marzi.pnh.)
RE: دو سوال در مورد درخت BST(درخت جستجوی دودویی)
سوال اول بنظرم چون گفته ارتفاع n-1 ،میشه درخت مورب پس مرتبه زمانی میشه n به توان ٢

سوال دوم رو هم تعداد مولفه های همبند گراف n+m میشه

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۷۸۴ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  سوال در مورد صفحه بندی در سیستم عامل Azadam ۱ ۱,۴۹۳ ۱۳ دى ۱۴۰۰ ۱۱:۰۴ ق.ظ
آخرین ارسال: Azadam
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۴۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۰۱ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۶۶ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  سوال در مورد سهمیه رتبه اولی rezamim2020 ۰ ۱,۹۲۴ ۱۶ شهریور ۱۳۹۹ ۰۴:۳۵ ب.ظ
آخرین ارسال: rezamim2020
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۲۹ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  در جستجوی اساتید امنیت wskf ۰ ۱,۸۵۱ ۱۸ فروردین ۱۳۹۹ ۰۸:۴۶ ب.ظ
آخرین ارسال: wskf
  تعداد درخت فراگیر ss311 ۰ ۲,۰۴۰ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  سوال در مورد دروس جبرای و چارت ارشد کامپیوتر/هوش دانشگاه تهران imali ۱ ۲,۸۲۵ ۰۴ مهر ۱۳۹۸ ۰۱:۴۶ ق.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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