تالار گفتمان مانشت

با سلام و احترام
دوستان خواهشا اطلاعاتی دارند ارائه بدن، ممنون میشم :
سوال 1 - بهترین زمان ممکن برای محاسبه ارتفاع درخت BST؟ الف - (h)O ب- (n)O ج - (lgn)O د - ج - (nlgn)O

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

با تشکر

(04 مهر 1396 10:39 ب.ظ)omidelf نوشته شده توسط: [ -> ]

(17 شهریور 1396 01:03 ب.ظ)امیدوار نوشته شده توسط: [ -> ]با سلام و احترام
دوستان خواهشا اطلاعاتی دارند ارائه بدن، ممنون میشم :
سوال ۱ - بهترین زمان ممکن برای محاسبه ارتفاع درخت BST؟ الف - (h)O ب- (n)O ج - (lgn)O د - ج - (nlgn)O

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

با تشکر

سلام

سوال ۱ :

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

سوال ۲ :

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

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

با تشکر از پاسخ شما

با سلام
لطفا به دو سوال بنده جواب دهید

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

log n n n^2 nlog n


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

nm n+m m nlogn+m

سپاس فراوان

سوال اول بنظرم چون گفته ارتفاع n-1 ،میشه درخت مورب پس مرتبه زمانی میشه n به توان ٢

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

اگه فک میکنین اشتباهه حتما شماهم نظرتونو بگین خوشحال میشم