(۱۸ آذر ۱۳۹۴ ۱۰:۰۹ ب.ظ)reza.bsh نوشته شده توسط:  مرتبه زمانی زیر چی میشه؟
چه راهی برای حلش دارین؟

$T(n)=T(\log n) 1$

با جایگذاری خیلی راحت میشه log *n

(۱۸ آذر ۱۳۹۴ ۱۰:۱۶ ب.ظ)sixsixsix نوشته شده توسط:  

(18 آذر ۱۳۹۴ ۱۰:۰۹ ب.ظ)reza.bsh نوشته شده توسط:  مرتبه زمانی زیر چی میشه؟
چه راهی برای حلش دارین؟

$T(n)=T(\log n) 1$

با جایگذاری خیلی راحت میشه log *n

log*n یعنی چی؟یعنی loglogn؟
آخه اینجور چیزی من تاحالا ندیدم.
ممنون

(۱۸ آذر ۱۳۹۴ ۱۰:۵۶ ب.ظ)reza.bsh نوشته شده توسط:  

(18 آذر ۱۳۹۴ ۱۰:۱۶ ب.ظ)sixsixsix نوشته شده توسط:  

(18 آذر ۱۳۹۴ ۱۰:۰۹ ب.ظ)reza.bsh نوشته شده توسط:  مرتبه زمانی زیر چی میشه؟
چه راهی برای حلش دارین؟

$T(n)=T(\log n) 1$

با جایگذاری خیلی راحت میشه log *n

log*n یعنی چی؟یعنی loglogn؟
آخه اینجور چیزی من تاحالا ندیدم.
ممنون

Log*n در واقع مساوی با چند بار از n باید log گرفت تا مساوی ۱ یا کمتر از یک بشه....
logloglogloglog......n که در واقع این رابطه بازگشتی هم همین رو میگه که از روش جایگذاری خیلی راحت اثبات میشه...

(۱۹ آذر ۱۳۹۴ ۱۲:۳۵ ق.ظ)g.norozi نوشته شده توسط:  

(18 آذر ۱۳۹۴ ۱۰:۵۶ ب.ظ)reza.bsh نوشته شده توسط:  

(18 آذر ۱۳۹۴ ۱۰:۱۶ ب.ظ)sixsixsix نوشته شده توسط:  

(18 آذر ۱۳۹۴ ۱۰:۰۹ ب.ظ)reza.bsh نوشته شده توسط:  مرتبه زمانی زیر چی میشه؟
چه راهی برای حلش دارین؟

$T(n)=T(\log n) 1$

با جایگذاری خیلی راحت میشه log *n

log*n یعنی چی؟یعنی loglogn؟
آخه اینجور چیزی من تاحالا ندیدم.
ممنون

Log*n در واقع مساوی با چند بار از n باید log گرفت تا مساوی ۱ یا کمتر از یک بشه....
logloglogloglog......n که در واقع این رابطه بازگشتی هم همین رو میگه که از روش جایگذاری خیلی راحت اثبات میشه...

ممنون از شما.
ولی خب نکته مهم اینه که این چند بار لگاریتم گرفتن دقیقا مرتبه زمانیش چنده؟یعنی چند بار باید از n لگاریتم گرفت تا به ۱ رسید؟
چون log*n فقط میگه که باید به یک تعدادی لگاریتم گرفت ولی نمیگه که این تعداد دقیقا چند تاست.
فکر میکنم برای حل اون رابطه بازگشتی باید اول این تعدادو بدست آورد.

سلام نگاه کن اصلا مهم نیست که شما پیدا کنی چند بار باید log بگیری...چون معمولا توی روابط بازگشتی به ما یک نقطه پایان میدن مثلا توی این سوال T(1)=1 معنی خوبی میده .... یعنی شما توی روش جایگذاری اونقدر جایگذاری میکنی که مثلا به یک ۲ به توان k برسی ...که اون ۲ به توان k رو میذاری ۱ ....معادله حل شد..نمیدونم چه قدر تونستم منظورمو برسونم...توی حل روابط بازگشتی همیشه یک نقطه پایان میده...

(۲۱ آذر ۱۳۹۴ ۱۱:۱۵ ب.ظ)g.norozi نوشته شده توسط:  سلام نگاه کن اصلا مهم نیست که شما پیدا کنی چند بار باید log بگیری...چون معمولا توی روابط بازگشتی به ما یک نقطه پایان میدن مثلا توی این سوال T(1)=1 معنی خوبی میده .... یعنی شما توی روش جایگذاری اونقدر جایگذاری میکنی که مثلا به یک ۲ به توان k برسی ...که اون ۲ به توان k رو میذاری ۱ ....معادله حل شد..نمیدونم چه قدر تونستم منظورمو برسونم...توی حل روابط بازگشتی همیشه یک نقطه پایان میده...

ممنون که جواب دادی

T(n)=T(logn)+1

برای اینکه ما تعداد صدا زدن های این تابع بازگشتی(مرتبه زمانی) رو بدست بیاریم باید بدونیم که t(n بعد از چند بار لگاریتم گرفتن به ۱ میرسه.درسته؟
log*n که شما گفتین برابر میشه با logloglog....logn در نهایت مقدار ۱ رو به ما میده که همون نقطه پایانه و ربطی به مرتبه زمانی نداره.
مثلا در تابع بازگشتی زیر
T(n)=T(n-1)+1
ما میدونیم که t(n بعد از n بار به ۰ میرسه.درنتیجه مرتبه زمانیش n میشه.
ولی حالا اگه جایگذاری کنم در نهایت به n-1-1-1-1...-1=0 میرسم که فقط نقطه پایانی رو به من میده.ولی چون من میدونم که این جایگذاری بعد ازn بار تموم میشه و به نقطه پایان میرسم،میتونم بفهمم که این تابع از مرتبه n است.

در مورد تابع باز گشتی
T(n)=T(logn)+1
نیز ما باید بدونیم که دقیقا بعد از چند بار لگاریتم گرفتن به نقطه پایانی میرسیم.در حالی که log*n این مهمو به ما نمیده ،و فقط خود نقطه پایانی رو به ما میده(که همون ۱میشه).