انجمنصفحه اولجستجوی انجمن

[امیدوار]

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

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

با تشکر

[امیدوار]

(۰۴ مهر ۱۳۹۶ ۱۰:۳۹ ب.ظ)omidelf نوشته شده توسط:  

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

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

با تشکر

سلام

سوال ۱ :

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

سوال ۲ :

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

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

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

[hamzadebaroon]

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

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

log n n n^2 nlog n


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

nm n+m m nlogn+m

سپاس فراوان

[marzi.pnh]

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

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

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