زمان کنونی: ۲۶ مهر ۱۳۹۶, ۰۲:۳۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

چند سوال از تحلیل الگوریتم ها

ارسال:
۰۸ بهمن ۱۳۹۰, ۰۹:۲۴ ب.ظ (آخرین ویرایش در این ارسال: ۰۸ بهمن ۱۳۹۰ ۰۹:۲۶ ب.ظ، توسط پشتکار.)
چند سوال از تحلیل الگوریتم ها
با سلام
۱- آیا درسته وقتی می گیم مثلا فلان الگوریتم مرتبه اش [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]
این علامت ستاره چیه؟
یافتن تمامی ارسال‌های این کاربر
ارسال:
۰۸ بهمن ۱۳۹۰, ۰۹:۴۶ ب.ظ (آخرین ویرایش در این ارسال: ۰۸ بهمن ۱۳۹۰ ۰۹:۵۰ ب.ظ، توسط Mohammad-A.)
RE: چند سوال از تحلیل الگوریتم ها
۱. بله درسته... طبق تعریف نماد 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 بگیریم تا به یک برسه. در اینجا حد پایین رو باید در نظر داشت.

Yesterday is History, Tomorrow is a Mystery but Today is a Gift
That is why it's called the Present
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: پشتکار
ارسال:
۰۸ بهمن ۱۳۹۰, ۰۹:۵۹ ب.ظ
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
یافتن تمامی ارسال‌های این کاربر
ارسال:
۰۹ بهمن ۱۳۹۰, ۰۶:۱۴ ب.ظ
چند سوال از تحلیل الگوریتم ها
خواهش می کنم اگه کسی میتونه کمکم کنه
یافتن تمامی ارسال‌های این کاربر
ارسال:
۰۹ بهمن ۱۳۹۰, ۰۷:۵۰ ب.ظ
چند سوال از تحلیل الگوریتم ها
ببینید توی اون بحث حداقل٬ روی الگوریتم‌هایی بحث شده بود که فقط با مقایسه٬ مرتب‌سازی انجام میشه. counting هم فکر میکنم تعداد عناصر را در یک بازه برمیگردانه.
اون موردی که برای سوال سوم هست٬ طبق قاعده‌ای هست که در کتاب‌های طراحی الگوریتم نوشته شده... کتاب یوسفی این مورد رو ذکر کرده.

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

Yesterday is History, Tomorrow is a Mystery but Today is a Gift
That is why it's called the Present
یافتن تمامی ارسال‌های این کاربر


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  آنالیز الگوریتم zr2358 ۳ ۱,۷۲۲ ۰۸ دى ۱۳۸۹ ۰۲:۱۰ ب.ظ
آخرین ارسال: لهمشد

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close