با سلام و احترام
دوستان خواهشا اطلاعاتی دارند ارائه بدن، ممنون میشم :
سوال ۱ - بهترین زمان ممکن برای محاسبه ارتفاع درخت 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 با توجه به این لینک :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
با تشکر از پاسخ شما
با سلام
لطفا به دو سوال بنده جواب دهید
۱-بهترین زمان ممکن که می توان با n ;کلید یک درخت جستجوی دودویی با ارتفاع دقیقا برابر n-1 ایجاد نمود کدام است؟
log n n n^2 nlog n
۲-پیچیدگی محاسباتی یافتن تعداد مولفه های همبندی یک گراف اسپارس با n نود و m یال
nm n+m m nlogn+m
سپاس فراوان
سوال اول بنظرم چون گفته ارتفاع n-1 ،میشه درخت مورب پس مرتبه زمانی میشه n به توان ٢
سوال دوم رو هم تعداد مولفه های همبند گراف n+m میشه
اگه فک میکنین اشتباهه حتما شماهم نظرتونو بگین خوشحال میشم
