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

مرتبه زمانی

ارسال:
  

H-Arshad پرسیده:

مرتبه زمانی

سلام بچه ها این چطور گفته تتا n ?? اخه حدش میگه صورت از مخرج بزرگ تر هست پس باید بشه O اون ، نه تتا اون
Saman، در تاریخ ۰۹ آبان ۱۳۹۵ ۱۰:۱۷ ب.ظ برای این مطلب یک پانوشت گذاشته است:

سلام
لطفا از این پس در جای مناسب تاپیک بگذارید که بعدا کاربران بتونن استفاده کنند.
با سپاس



فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Pure Liveliness پاسخ داده:

RE: مرتبه زمانی

(۰۹ آبان ۱۳۹۵ ۰۵:۲۶ ب.ظ)H-Arshad نوشته شده توسط:  سلام بچه ها این چطور گفته تتا n ?? اخه حدش میگه صورت از مخرج بزرگ تر هست پس باید بشه O اون ، نه تتا اون
سلام. نسبت حدشون که عدد ثابت [tex]\sqrt{۱۰}[/tex] شده پس یعنی هم رشد هستن.
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

H-Arshad پاسخ داده:

مرتبه زمانی

ممنون فقط اگر بی نهایت شد، میگیم رشد صورت بیشتر از مخرج هست...اگر صفر شد . برعککس درسته؟
اگر عدد شد، میگیم هم رشد هستند ؟
نقل قول این ارسال در یک پاسخ

ارسال:
  

Pure Liveliness پاسخ داده:

RE: مرتبه زمانی

(۰۹ آبان ۱۳۹۵ ۱۱:۰۴ ب.ظ)H-Arshad نوشته شده توسط:  ممنون فقط اگر بی نهایت شد، میگیم رشد صورت بیشتر از مخرج هست...اگر صفر شد . برعککس درسته؟
اگر عدد شد، میگیم هم رشد هستند ؟
خواهش میکنم.
بله. همین طور هست.
اگه وقتی n به سمت بی نهایت میره صورت و مخرج هر دو صفر یا بی نهایت بشن، مشتق میگیریم. اگه نه هم که مثل اینجا نیازی به مشتق نیست.
[tex]\lim_{n\longrightarrow\infty}\: (\frac{f(n)}{g(n)})=c\: (constant)\: \: \longrightarrow f(n)\in\theta(g(n))[/tex]
[tex]\lim_{n\longrightarrow\infty}\: (\frac{f(n)}{g(n)})=0\: \: \longrightarrow f(n)\in O(g(n))[/tex]
[tex]\lim_{n\longrightarrow\infty}\: (\frac{f(n)}{g(n)})=\infty\: \: \longrightarrow f(n)\in\Omega(g(n))[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

H-Arshad پاسخ داده:

RE: مرتبه زمانی

برای اینکه مجدد موضوع ایجاد نشه همین جا پرسیدم ...ببنید من یک جا خیلی گیج میشم...مثلا برای مقایسه این دوتا از دو طرف Ln گرفته و فک کنم درست هم بدست اومده(اگر واضح نیست لطفا بفرمایید تا بازنویسی کنمش و بزارم)
یکجا هم حد میگیریم در بی نهایت...من از کجا بفهمم -کجا نیاز هست حد بگیرم و کجا این طور Ln بگیرم؟ که راه اشتباه نرم...


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Pure Liveliness پاسخ داده:

RE: مرتبه زمانی

چند تا راه وجود داره.
یکیش حد هست که توی پست قبلی گفتم چطور میشه با استفاده از حد گرفتن دو تا تابع رو مقایسه کرد. (حد گرفتن توی بی نهایت هم واضح هست که دو تا تابع رو وقتی n شون(متغیرشون) میره به سمت بی نهایت با هم مقایسه میکنیم. وگرنه مثلا توی مقایسه ی [tex]2^n[/tex] و [tex]n^2[/tex] تا یه جایی [tex]n^2[/tex] بزرگتر هست اما از یه [tex]n_0[/tex] ای به بعد[tex]2^n[/tex] بیشتر هست. یعنی توی n به سمت بی نهایت مهمه مقایسه ی دو تا تابع)
یکیش لگاریتم گرفتن هست که شرایط زیر پیش میاد:
[tex]\log(f(n))\: >\: \log(g(n))[/tex] در نتیجه رشد تابع f بیشتر هست.
[tex]\log(f(n))\: <\: \log(g(n))[/tex] در نتیجه رشد تابع g بیشتر هست.
[tex]\log(f(n))\: =\: \log(g(n))[/tex] اصلا نمیشه گفت رشد کدوم یکی بیشتر هست. مثل مقایسه ی [tex]n^2[/tex] و [tex]n^3[/tex] که رشد لگاریتم هر دو تاشون برابر میشه و نمیتونیم بگیم که کدوم بیشتر هست. یا مساوی هستن.
راه دیگه که بیشتر کاربرد داره یه سری ساده سازی ها هست که توابع رو مثلا به فرم هم در بیاریم.
این که از کدوم راه بریم واسه توابع مختلف فرق داره و فقط با تمرین زیاد میتونید بگید که بهتره چطوری توابع رو مقایسه کنید.
این سوال رو کاملا درست حل کردید (البته فرقی نمیکنه نسبت به چه پایه ای لگاریتم بگیرید ولی معمولا لگاریتم در مبنای ۲ میگیرن و این باعث میشه گاهی بعضی توابع با این پایه ساده تر بشه نوشتشون.) بعد هم واسه این تابع حد گرفتن و بعدش مشتق (حد بی نهایت روی بی نهایت و استفاده از قاعده ی هوپیتال) سخت میشه و البته میشه هم به صورت n به توان یه چیزی نوشت جفتشون رو و مقایسه کرد.) اینجا انگار لگاریتم گرفتن راحت تره.
میخواید اگه به سوالی برخورد کردید که نمیدونستید از کدوم راه برید همین جا بگید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۲ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۴ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۵۶۸ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۴۰۹ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۳,۲۸۵ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۵۰۶ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  مرتبه زمانی Sanazzz ۰ ۱,۸۲۹ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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