سلام
بچه ها میشه نشون بدید پیدا کردن نزدیک ترین عدد در لیست به یک عدد دلخواه از Omega lognاست.
(۲۸ دى ۱۳۹۳ ۰۷:۵۷ ق.ظ)Imankhani نوشته شده توسط: سلاماگه منظورتون اینه که نزدیکترین عدد به یک عدد دلخواه از n عدده واسه منم جالبه چجوری ممکنه کمتر از
بچه ها میشه نشون بدید پیدا کردن نزدیک ترین عدد در لیست به یک عدد دلخواه از Omega lognاست.
کد:
O(n)(۲۸ دى ۱۳۹۳ ۰۵:۰۷ ب.ظ)artmiss نوشته شده توسط:(28 دى ۱۳۹۳ ۰۷:۵۷ ق.ظ)Imankhani نوشته شده توسط: سلاماگه منظورتون اینه که نزدیکترین عدد به یک عدد دلخواه از n عدده واسه منم جالبه چجوری ممکنه کمتر از
بچه ها میشه نشون بدید پیدا کردن نزدیک ترین عدد در لیست به یک عدد دلخواه از Omega lognاست.انجام بشه. مگر اینکه لیست مرتب باشه و به روش جستجوی دودویی بخواهیم عمل کنیم.کد:
O(n)
لیست مرتب نیس. تو کتاب دکتر قدسی ی ایده داده با درخت تصمیم میشه نشون داد ولی ایده ای برای حلش ندارم.
(۲۸ دى ۱۳۹۳ ۰۸:۲۲ ب.ظ)Imankhani نوشته شده توسط: لیست مرتب نیس. تو کتاب دکتر قدسی ی ایده داده با درخت تصمیم میشه نشون داد ولی ایده ای برای حلش ندارم.
چه جالب این سوالو قبلا تو کتاب دیده بودم ولی قانع نشدم به جوابش علامت زدم که دو باره بخونم الان که رفتم خوندم میبینم اشتباه شده احتمالن اشتباه چاپی بوده و ! چاپ نشده.
به دو دلیل
۱- دکتر قدسی تو اسلایداشون گفتن کران پایین درخت تصمیم !logn هست
۲- اگه دقت کنی کتاب میگه مشابه استدلالی که برای بدست آوردن کران پایین الگوریتم مرتب سازی انجام شده است میبینیم که کران پایین پنین الگوریتمی logn است امام ما میدونیم که کران پایین الگوریتم های مرتب سازی (مقایسه ای) !nlogn=logn هست.
پس نه logn و نه n
یعنی کمتر از nlgn امکان نداره
(۲۸ دى ۱۳۹۳ ۰۸:۳۸ ب.ظ)artmiss نوشته شده توسط:(28 دى ۱۳۹۳ ۰۸:۲۲ ب.ظ)Imankhani نوشته شده توسط: لیست مرتب نیس. تو کتاب دکتر قدسی ی ایده داده با درخت تصمیم میشه نشون داد ولی ایده ای برای حلش ندارم.
چه جالب این سوالو قبلا تو کتاب دیده بودم ولی قانع نشدم به جوابش علامت زدم که دو باره بخونم الان که رفتم خوندم میبینم اشتباه شده احتمالن اشتباه چاپی بوده و ! چاپ نشده.
به دو دلیل
۱- دکتر قدسی تو اسلایداشون گفتن کران پایین درخت تصمیم !logn هست
۲- اگه دقت کنی کتاب میگه مشابه استدلالی که برای بدست آوردن کران پایین الگوریتم مرتب سازی انجام شده است میبینیم که کران پایین پنین الگوریتمی logn است امام ما میدونیم که کران پایین الگوریتم های مرتب سازی (مقایسه ای) !nlogn=logn هست.
پس نه logn و نه n
یعنی کمتر از nlgn امکان نداره
مرسی منم تعجب کردم. ممنون از پیگیریتون.
