پیچیدگی زمانی توابع در حالت Big-o

[raranjbar]

پیچیدگی زمانی توابع زیر در حالت Big-O چی میشه البته اگه با اثبات بگید بهتره؟


http://up.iranblog.com/Files73/bcbaf3393d2e493fa7c8.jpg

[raranjbar]

یکی جواب بده :ناراحت:

[mohsensaghafi]

سلام دوست عزیز.
اولی
O(n) هست و دومی
O(log(n))
موفق و پیروز

[raranjbar]

سلام دوست عزیز.
اولی
O(n) هست و دومی
O(log(n))
موفق و پیروز

ممنون میشه با اثبات بگید؟

[مسعود اقدسی فام]

سلام دوست عزیز.
اولی
O(n) هست و دومی
O(log(n))موفق و پیروز

ولی به نظر من دومی هم ( O( n می‌شه. به ضریب 2 کنار جمله n / 2 توجه کنید.

[mohsensaghafi]

ولی به نظر من دومی هم ( O( n می‌شه. به ضریب 2 کنار جمله n / 2 توجه کنید.

سلام دوست عزیز.
ضرایب ثابت در پیچیدگی ها تاصیر ندارند. چون به سادگی از تابع big-o خارج می شوند.
اگر هم درون پیچیدگی بیایند به این صورت نخواهند بود.


O(2f(n/2)) => O(f(2n/2)) => O(n)

در حالی که عبارت به این صورت صحیح می باشد.


O(2f(n/2)) => 2 O(f(n/2)) => 2 O(lon(n))

که خوب پر واضح است که ضریب 2 از این میان حذف می شود.
به علاوه. از نظر اجرای کد پیاده سازی شده اگر بحث کنیم، تابع برای مقادیر n/2 صدا زده می شود و حاصل در 2 ضرب می شود. در این حالت فقط یک بار تابع صدا زده شده است. و با توجه به n/2 در هر مرحله بزرگی مسئله ما در حال نصف شدن است که این نصف شدن قطعا پیچیدگیی در حد log(n) خواهد داشت.
اگر توضیحات قانع کننده نیست، لطفا بگویید تا توضیحات کاملتری ارائه نمایم.
موفق و پیروز

[مسعود اقدسی فام]

سلام دوست عزیز.
ضرایب ثابت در پیچیدگی ها تاصیر ندارند. چون به سادگی از تابع big-o خارج می شوند.
اگر هم درون پیچیدگی بیایند به این صورت نخواهند بود.


O(2f(n/2)) => O(f(2n/2)) => O(n)
در حالی که عبارت به این صورت صحیح می باشد.


O(2f(n/2)) => 2 O(f(n/2)) => 2 O(lon(n))
که خوب پر واضح است که ضریب 2 از این میان حذف می شود.
به علاوه. از نظر اجرای کد پیاده سازی شده اگر بحث کنیم، تابع برای مقادیر n/2 صدا زده می شود و حاصل در 2 ضرب می شود. در این حالت فقط یک بار تابع صدا زده شده است. و با توجه به n/2 در هر مرحله بزرگی مسئله ما در حال نصف شدن است که این نصف شدن قطعا پیچیدگیی در حد log(n) خواهد داشت.
اگر توضیحات قانع کننده نیست، لطفا بگویید تا توضیحات کاملتری ارائه نمایم.
موفق و پیروز

شما پیچیدگی محاسبه خود تابع رو نوشتید. اما من منظورم حالتی بود که این تابع پیچیدگی یه سری عملیات رو نشون می‌ده و من با حل رابطه و به دست آوردن فرمول محاسبه مستقیم، پیچیدگی اون سری عملیات مد نظرم بود. واسه همین به دو جواب متفاوت رسیدیم. :چشمک:

ممنون بابت توضیحات. :لبخندساده:

[mohsensaghafi]

شما پیچیدگی محاسبه خود تابع رو نوشتید. اما من منظورم حالتی بود که این تابع پیچیدگی یه سری عملیات رو نشون می‌ده و من با حل رابطه و به دست آوردن فرمول محاسبه مستقیم، پیچیدگی اون سری عملیات مد نظرم بود. واسه همین به دو جواب متفاوت رسیدیم. :چشمک:

ممنون بابت توضیحات. :لبخندساده:

سلام دوست عزیز.
من از جمله ای که گفتید واقعا چیزی نفهمیدم. چیزی رو که من جل کردم یک رابطه بازگشتی بود که پیچیدگیش رو محاسبه کردم.
در ضمن پیجیدگی رو با T نشون نمی دن.
خوشحال شدم از آشناییتون.
موفق باشید.

[masoud05]

فکر کنم دوست من اشتباه می کنین چونکه به رابطه بازگشتی برج هانوی دقت کنید:

T(n) = 2T(n-1)+1
که جوابش میشه

(

O(2^n
پس ضریب مهمه اما طبق قضیه مادر (Master):

a=2 , b=2 , c=O(1)=n^0
که جواب میشه:

O(n)

[mohsensaghafi]

فکر کنم دوست من اشتباه می کنین چونکه به رابطه بازگشتی برج هانوی دقت کنید:

T(n) = 2T(n-1)+1
که جوابش میشه

(

O(2^n
پس ضریب مهمه اما طبق قضیه مادر (Master):

a=2 , b=2 , c=O(1)=n^0
که جواب میشه:

O(n)

سلام دوست عزیز.
این مسئله به نظرم بیشتر از اونکه به پیچیدگی برج هانوی شبیه باشه به MergeSort شبیهه.
در مسئله ، طول n داره هر بار نصف می شه. این نصف شدن برای شما هیچ معنایی نداره؟ شما رو به یاد O(log(n)) نمی اندازه؟!
موفق و پبروز