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

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

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  بهترین گرایش برای موقعیت شغلی تحلیل سیستم shahabkarimi00 ۳ ۲,۱۱۵ ۰۹ آذر ۱۳۹۹ ۰۳:۳۵ ب.ظ
آخرین ارسال: mohammadasadi1
  مدیریت سیستم چند پردازنده ای متقارن no_ta2000 ۰ ۳۲۶ ۰۹ مهر ۱۳۹۹ ۰۲:۲۱ ب.ظ
آخرین ارسال: no_ta2000
  خواص محیط برای عامل سیستم تحلیل تصاویر پزشکی Ali1991khe ۶ ۹۱۳ ۰۴ مهر ۱۳۹۹ ۰۸:۳۲ ق.ظ
آخرین ارسال: Ali1991khe
  صفحه چند سطحی Flash1 ۰ ۴۲۱ ۱۰ تیر ۱۳۹۹ ۰۵:۵۸ ب.ظ
آخرین ارسال: Flash1
  در مصاحبه کارشناس تحلیل گر سیستم چه می پرسند؟ سیما ۱۹۵۶ ۲۸ ۳۰,۸۲۹ ۱۳ اسفند ۱۳۹۸ ۱۱:۴۹ ق.ظ
آخرین ارسال: alma1988
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۶۵۶ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
  کمک برای چند تا سوالات شبکه کامپیوتری Hamedudk ۳ ۲,۱۳۲ ۲۷ آبان ۱۳۹۸ ۱۱:۴۲ ق.ظ
آخرین ارسال: khayyam
  منابع تخصصی شغل تحلیل گر سیستم Hamedudk ۱ ۱,۳۳۸ ۰۷ آبان ۱۳۹۸ ۰۱:۰۸ ق.ظ
آخرین ارسال: marvelous
  بهترین منابع برای تحلیل اقتصادی کدامند؟ hoseyn9999so ۰ ۱,۹۵۴ ۱۶ مهر ۱۳۹۸ ۰۶:۴۵ ق.ظ
آخرین ارسال: hoseyn9999so
  افزایش واگرایی الگوریتم های مبتنی بر جمعیت moslem73421 ۲ ۹۰۱ ۰۵ شهریور ۱۳۹۸ ۱۰:۵۳ ب.ظ
آخرین ارسال: cpt.mazi

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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