انجمنصفحه اولجستجوی انجمن

[پشتکار]

با سلام
۱- آیا درسته وقتی می گیم مثلا فلان الگوریتم مرتبه اش $O(n^{2})$ است یعنی یا خود n^2 است یا کمتر از n^2؟

۲- هر الگوریتم مرتب سازی مقایسه ای از مرتبه $\Omega (nlogn)$ است!
این رو در کتابی دیدم. ولی ما الگوریتم با مرتبه n هم داریم که!!! منظورش چیه مگه؟

۳- آیا تابع $\left \lceil logn \right \rceil!$ دارای کران چند جمله ای است؟ (منظور از کران چند جمله ای چیه؟)

۴- کدام تابع بطور مجانبی بزرگتر است؟ $log(log^{*}n)$
یا $log^{*}(logn)$
این علامت ستاره چیه؟

[Mohammad-A]

۱. بله درسته... طبق تعریف نماد big_o این رابطه برقرار هست. تابعی باید باشه که رشدش در یک نقطه‌ای بیشتر از تابع اصلی ما باشه.

۲. این موضوع درباره‌ی الگوریتم‌های مرتب‌سازی‌ای هست که فقط با مقایسه کلیدها رو مرتب می‌کنند. در بدترین حالت حداقل $\left \lceil \right logn!\rceil \to \Omega (nlogn)$

۳. اگر تابعی مثل F(x بخواد محدود به چند جمله‌ای باشه٬ باید از قاعده‌ی زیر پیروی کنه.
$log(F(n))=O(logn)$
برای تابعی که داریم:
$log\left \lceil \right logn\rceil‌! = \Theta (logn.loglogn) \to \left \lceil \right logn\rceil‌! \neq O(logn)$


۴. علامت ستاره روی لگاریتم به این معناست که در واقع چند بار از عددی که به لگاریتم داده‌ایم باید log بگیریم تا به یک برسه. در اینجا حد پایین رو باید در نظر داشت.

[پشتکار]

(۰۸ بهمن ۱۳۹۰ ۱۰:۴۶ ب.ظ)mam نوشته شده توسط:  ۲. این موضوع درباره‌ی الگوریتم‌های مرتب‌سازی‌ای هست که فقط با مقایسه کلیدها رو مرتب می‌کنند. در بدترین حالت حداقل $\left \lceil \right logn!\rceil \to \Omega (nlogn)$

مثلا radix , counting رو شامل نمیشه ولی هیپ و سریع و ادغامی رو شامل میشه؟ درست متوجه شدم؟

(۰۸ بهمن ۱۳۹۰ ۱۰:۴۶ ب.ظ)mam نوشته شده توسط:  ۳. اگر تابعی مثل F(x بخواد محدود به چند جمله‌ای باشه٬ باید از قاعده‌ی زیر پیروی کنه.
$log(F(n))=O(logn)$
برای تابعی که داریم:

چرا؟ باید محدود بشه؟ اینو از کجا آوردید؟

(۰۸ بهمن ۱۳۹۰ ۱۰:۴۶ ب.ظ)mam نوشته شده توسط:  ۴. علامت ستاره روی لگاریتم به این معناست که در واقع چند بار از عددی که به لگاریتم داده‌ایم باید log بگیریم تا به یک برسه. در اینجا حد پایین رو باید در نظر داشت.

خب اینطوری که گفتید هر دوتا مثل هم میشن که

[پشتکار]

خواهش می کنم اگه کسی میتونه کمکم کنه

[Mohammad-A]

ببینید توی اون بحث حداقل٬ روی الگوریتم‌هایی بحث شده بود که فقط با مقایسه٬ مرتب‌سازی انجام میشه. counting هم فکر میکنم تعداد عناصر را در یک بازه برمیگردانه.
اون موردی که برای سوال سوم هست٬ طبق قاعده‌ای هست که در کتاب‌های طراحی الگوریتم نوشته شده... کتاب یوسفی این مورد رو ذکر کرده.

برای مورد چهارم٬ مثلاً فرض کنید بخوایم لگاریتم-استار ۳۲ رو بگیریم. جواب میشه ۴... چون اگر یک بار لگاریتم بگیریم٬ میشه ۱۶ - دوباره میشه ۴ سه بار میشه ۲ و چهار بار میشه ۱