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

مرتبه زمانی

ارسال:
  

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۷۰۱ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۷۱۰ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  مرتبه زمانی Sanazzz ۱۶ ۳,۷۵۳ ۲۸ اسفند ۱۳۹۷ ۱۲:۲۴ ب.ظ
آخرین ارسال: npour
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۶۶۷ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  مرتبه زمانی Sanazzz ۰ ۳۵۸ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz
  مشکل در پیچیدگی زمانی ماهی ۲۵۸ ۲ ۸۴۲ ۲۳ تیر ۱۳۹۷ ۱۲:۱۸ ق.ظ
آخرین ارسال: Alisalar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۲,۱۱۲ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  مشکل در محاسبه مرتبه ایک سوال Mr.R3ZA ۰ ۴۷۵ ۲۴ خرداد ۱۳۹۷ ۰۱:۰۳ ب.ظ
آخرین ارسال: Mr.R3ZA
  سوال ۱۱۵- مهندسی ۹۶- منطق مرتبه اول mzi ۰ ۳۷۰ ۲۱ فروردین ۱۳۹۷ ۰۵:۰۵ ب.ظ
آخرین ارسال: mzi
  نمودار زمانی مدار میلی! AEM4949 ۱۰ ۳,۵۵۹ ۰۹ اسفند ۱۳۹۶ ۰۳:۱۵ ب.ظ
آخرین ارسال: aminfaraji

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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