سلام و وقت بخیر .
[tex]T(n)=T(n-K)+O(Lgn)\: \: \: ,\: \: K\ge1[/tex]
(۰۴ فروردین ۱۳۹۶ ۰۲:۳۵ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر .مثلا" اگه k=1 بشه کران بالای این رابطه بصورت زیر حساب میشه :
[tex]T(n)=T(n-K)+O(Lgn)\: \: \: ,\: \: K\ge1[/tex]
[tex]if\: k=1\: T(n)=T(n-1)+\log n\: =\log n\: +\: \log(n-1)+...+\log(1)=\log(n\times n-1\times...\times1)=\log(n!)=nlogn[/tex]
پس میدونیم O(nlogn) میشه
(۰۴ فروردین ۱۳۹۶ ۰۴:۰۳ ب.ظ)arash691 نوشته شده توسط:(04 فروردین ۱۳۹۶ ۰۲:۳۵ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر .مثلا" اگه k=1 بشه کران بالای این رابطه بصورت زیر حساب میشه :
[tex]T(n)=T(n-K)+O(Lgn)\: \: \: ,\: \: K\ge1[/tex]
[tex]if\: k=1\: T(n)=T(n-1)+\log n\: =\log n\: +\: \log(n-1)+...+\log(1)=\log(n\times n-1\times...\times1)=\log(n!)=nlogn[/tex]
پس میدونیم O(nlogn) میشه
سلام . ممنون از پاسختون ، ولی من فکر میکنم این کران بالا که شما ذکر کردید در اینجا صادق نیست ، یعنی تا جایی که خودم پیش رفتم باید K رو زوج و فرد کنی و حل کنی ...
اگه درخت بازگشت براش رسم کنید توی هر سطح log n کنار گذاشته میشه و طول درخت بازگشت هم میشه قدر پایین n/k . همون میشه n log n
محاسبه ی دقیقش هم میشه قدر پایین n/k در log n
(۰۴ فروردین ۱۳۹۶ ۰۶:۰۹ ب.ظ)alireza01 نوشته شده توسط:(04 فروردین ۱۳۹۶ ۰۴:۰۳ ب.ظ)arash691 نوشته شده توسط:(04 فروردین ۱۳۹۶ ۰۲:۳۵ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر .مثلا" اگه k=1 بشه کران بالای این رابطه بصورت زیر حساب میشه :
[tex]T(n)=T(n-K)+O(Lgn)\: \: \: ,\: \: K\ge1[/tex]
[tex]if\: k=1\: T(n)=T(n-1)+\log n\: =\log n\: +\: \log(n-1)+...+\log(1)=\log(n\times n-1\times...\times1)=\log(n!)=nlogn[/tex]
پس میدونیم O(nlogn) میشه
سلام . ممنون از پاسختون ، ولی من فکر میکنم این کران بالا که شما ذکر کردید در اینجا صادق نیست ، یعنی تا جایی که خودم پیش رفتم باید K رو زوج و فرد کنی و حل کنی ...
اشتباه تحلیل کردید، این جور مواقع حتی به جای K اگه ۲K هم بذارید از نظر مرتبهی زمانی تفاوتی حاصل نمیشه، چه برسه به اینکه K زوج باشه یا فرد. اگه تابع رو باز کنید به صورت [tex]\log(n)+\log(n-k)+\log(n-2k)+...+\log(n-(\frac{n}{k}-1)\times k)+\log(n-\frac{n}{k}\times k)[/tex] میشه. البته اون جملهی آخر رو برای بهتر متوجه شدن نوشتم و الا نباید ظاهر بشه چون داخل لگاریتم صفر میشه.
به تعداد [tex]\frac{n}{k}[/tex] جمله داریم که نصف اونها از [tex]\log(\frac{n}{2})[/tex] بزرگتر خواهند بود. پس کل عبارت از [tex]\frac{n}{k}\times\frac{1}{2}\times\log(\frac{n}{2})[/tex] بزرگتر هست، از طرفی تمامی این [tex]\frac{n}{k}[/tex] جمله (به جز اولی) از [tex]\log(n)[/tex] کمتر هستند. پس کل عبارت از [tex]\frac{n}{k}\times\log(n)[/tex] کمتر هست. پس مرتبه میشه [tex]\frac{n}{k}\times\log(n)[/tex]. اون k رو هم بهتر هست بنویسیم چون اگه k بزرگ باشه، مثلاً [tex]\frac{n}{100}[/tex] در اون موقع مرتبه میشه [tex]\log(n)[/tex]
(۰۴ فروردین ۱۳۹۶ ۰۷:۳۲ ب.ظ)Behnam نوشته شده توسط: اشتباه تحلیل کردید، این جور مواقع حتی به جای K اگه ۲K هم بذارید از نظر مرتبهی زمانی تفاوتی حاصل نمیشه، چه برسه به اینکه K زوج باشه یا فرد. اگه تابع رو باز کنید به صورت [tex]\log(n)+\log(n-k)+\log(n-2k)+...+\log(n-(\frac{n}{k}-1)\times k)+\log(n-\frac{n}{k}\times k)[/tex] میشه. البته اون جملهی آخر رو برای بهتر متوجه شدن نوشتم و الا نباید ظاهر بشه چون داخل لگاریتم صفر میشه.ممنون استاد.
به تعداد [tex]\frac{n}{k}[/tex] جمله داریم که نصف اونها از [tex]\log(\frac{n}{2})[/tex] بزرگتر خواهند بود. پس کل عبارت از [tex]\frac{n}{k}\times\frac{1}{2}\times\log(\frac{n}{2})[/tex] بزرگتر هست، از طرفی تمامی این [tex]\frac{n}{k}[/tex] جمله (به جز اولی) از [tex]\log(n)[/tex] کمتر هستند. پس کل عبارت از [tex]\frac{n}{k}\times\log(n)[/tex] کمتر هست. پس مرتبه میشه [tex]\frac{n}{k}\times\log(n)[/tex]. اون k رو هم بهتر هست بنویسیم چون اگه k بزرگ باشه، مثلاً [tex]\frac{n}{100}[/tex] در اون موقع مرتبه میشه [tex]\log(n)[/tex]