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

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال در مورد صفحه بندی در سیستم عامل Azadam ۱ ۳۷۸ ۱۳ دى ۱۴۰۰ ۱۱:۰۴ ق.ظ
آخرین ارسال: Azadam
  زمان جستجوی درخت fateme.sm ۰ ۷۷۳ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۱,۷۸۹ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: 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