تالار گفتمان مانشت
چند سوال از تحلیل الگوریتم ها - نسخه‌ی قابل چاپ

چند سوال از تحلیل الگوریتم ها - پشتکار - ۰۸ بهمن ۱۳۹۰ ۱۰:۲۴ ب.ظ

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

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

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

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

RE: چند سوال از تحلیل الگوریتم ها - Mohammad-A - 08 بهمن ۱۳۹۰ ۱۰:۴۶ ب.ظ

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

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

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


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

RE: چند سوال از تحلیل الگوریتم ها - پشتکار - ۰۸ بهمن ۱۳۹۰ ۱۰:۵۹ ب.ظ

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

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

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

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


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

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

چند سوال از تحلیل الگوریتم ها - پشتکار - ۰۹ بهمن ۱۳۹۰ ۰۷:۱۴ ب.ظ

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

چند سوال از تحلیل الگوریتم ها - Mohammad-A - 09 بهمن ۱۳۹۰ ۰۸:۵۰ ب.ظ

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

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