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

دو سوال در مورد درخت 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
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ


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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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