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

مرتبه زمانی

ارسال:
  

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 به توان یه چیزی نوشت جفتشون رو و مقایسه کرد.) اینجا انگار لگاریتم گرفتن راحت تره.
میخواید اگه به سوالی برخورد کردید که نمیدونستید از کدوم راه برید همین جا بگید.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتبه مانی Sanazzz ۳ ۴۵۱ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  مرتبه زمانی یافتن قطر Sepideh96 ۱ ۵۱۲ ۲۴ خرداد ۱۳۹۷ ۰۱:۱۸ ب.ظ
آخرین ارسال: Mr.R3ZA
  مشکل در محاسبه مرتبه ایک سوال Mr.R3ZA ۰ ۳۶۲ ۲۴ خرداد ۱۳۹۷ ۰۱:۰۳ ب.ظ
آخرین ارسال: Mr.R3ZA
  پیچیدگی زمانی Alirezaj ۰ ۴۳۳ ۰۷ آذر ۱۳۹۶ ۱۰:۰۶ ق.ظ
آخرین ارسال: Alirezaj
  اردر زمانی ومکانی یک درخت mostafaheydar ۰ ۵۱۲ ۲۹ اردیبهشت ۱۳۹۶ ۰۴:۳۲ ق.ظ
آخرین ارسال: mostafaheydar
  یافتن مرتبه زمانی ali.majed.ha ۲ ۶۳۲ ۱۹ اسفند ۱۳۹۵ ۰۵:۲۹ ب.ظ
آخرین ارسال: ali.majed.ha
  محاسبه ی مرتبه ی زمانی تابع life24 ۲ ۱,۰۰۴ ۲۶ دى ۱۳۹۵ ۰۴:۴۲ ب.ظ
آخرین ارسال: alireza01
  تحلیل مرتبه زمانی دو الگوریتم H-Arshad ۴ ۱,۰۶۳ ۰۸ آذر ۱۳۹۵ ۰۲:۰۶ ب.ظ
آخرین ارسال: Saman
  تحلیل زمانی دو حلقه تو در تو H-Arshad ۱ ۸۱۸ ۱۰ آبان ۱۳۹۵ ۰۲:۳۲ ق.ظ
آخرین ارسال: Behnam‌
  آنالیز زمانی این برنامه؟ JetiX ۱ ۵۵۹ ۲۳ مهر ۱۳۹۵ ۰۸:۱۶ ب.ظ
آخرین ارسال: Pure Liveliness

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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