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

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

ارسال:
  

H-Arshad پرسیده:

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

سلام بچه ها این دو الگوریتم میشه بگید چجوری حساب کرده؟ اخه داخل سیگما log هست و من تریس میکنم اصلا جور در نمیاد Sad توروخدا کمک


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


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

۰
ارسال:
  

Saman پاسخ داده:

RE: تحلیل مرتبه زمانی دو الگوریتم

سلام

ببینید، شما i=1 قرار میدهید. بعد به حلقه ی داخلی وارد میشوید. و به اندازه ی i حلقه ی داخلی رو اجرا میکنید.

بعد دقت کنید که خود i میتونه تا n اجرا بشه.

۱)فرض کنیم i=1 باشد.شما j را یک بار اجرا میکنید دستور بعدی آن را هم اجرا کرده از حلقه خارج میشوید.
===
۲)حالا i=2 باشد ، شما از j=1 تا زمانی که j<=2 باشد حلقه ی داخلی را اجرا میکنید. فقط دقت کنید که وقتی در این حلقه میچرخید j هر بار دو برابر می شود. حالا به ازای j=1 شرط برقرار است و یک اجرا داریم.سپس شما j*=2 را انجام دهید که مقدار j=2 میشود. باز هم شرط حلقه برقرار است و یک اجرای دیگر نیز داریم.(این شد دو تا اجرا) در چرخش بعد در داخل همین حلقه شرط دیگر برقرار نیست. و از حلقه خارج میشویم.

۳) سپس i=3 میشود
باز هم به حلقه ی داخلی وارد می شویم.و به ازای j=1 تا زمانی که j<=3 به اجرای حلقه می پردازیم، چون j هر بار دو برابر میشود باز هم با دو اجرا از حلقه داخلی خارج میشویم.

۴)سپس i=4
باز هم به حلقه ی داخلی وارد می شویم و به ازای j=1 تا زمانی که j<=4 به اجرای حلقه می پردازیم داریم، به ازای j=1 شرط برقرار است و یک اجرا داریم، سپس j*=2 میشود و باز هم شرط برقرار است به شکل مقابل ( ۴=>2 ) ، سپس دوباره j*=2 را انجام میدهیم و باز هم شرط برقرار است یعنی داریم ( ۴>=4) ، یعنی سه اجرا به ازای i=4 در دور بعدی از حلقه خارج می شویم . . .

۵)مقدار i=5 الی آخر . . .

به صورت تقریبی میشود حدس زد که ما مجموعِ [tex]\log i[/tex] تا اجرا داریم. با حد بالای n ، چرا که i خودش تا n پیش میرود . . .

زمان اجرا ها به ازای مقادیر i :
[tex]1\: +2+2+3+3\: .\: .\: .[/tex]

همین که در حلقه داخلی j هر بار دو برابر میشود و حد بالای j را i در نظر گرفته ایم یعنی اینکه به اندازه ی مجموع لگاریتم i با حدود i به اجرای حلقه داخلی j می پردازیم.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: تحلیل مرتبه زمانی دو الگوریتم

Big GrinBig Grin
سلام

اینو ببین

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

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

RE: تحلیل مرتبه زمانی دو الگوریتم

راستش محاسبه و ریاضی اش به کنار...من اصلا نمیدانم تحیلیش رو چرا این جور نوشته؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

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

RE: تحلیل مرتبه زمانی دو الگوریتم

راستش مشکل من با این هست که چون حلقه داخلی در عدد ۲ ضرب میشه پس گفتیم گام اون لگاریتمی هست درسته؟
الان در سیگما گفته logi یعنی پس لگاریتم اعداد ۳ ۵ ۷ ۹ ۱۱ ۱۳ ۱۵ ۱۷ و ... هم توش حساب میشه... و این جور جمع ش عوض میشه
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتبه زمانی Sanazzz ۱۷ ۴,۲۶۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۸۴ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  در مصاحبه کارشناس تحلیل گر سیستم چه می پرسند؟ سیما ۱۹۵۶ ۲۸ ۲۳,۲۲۷ ۱۳ اسفند ۱۳۹۸ ۱۱:۴۹ ق.ظ
آخرین ارسال: alma1988
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۲۲۲ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۸۱۷ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  منابع تخصصی شغل تحلیل گر سیستم Hamedudk ۱ ۴۷۰ ۰۷ آبان ۱۳۹۸ ۰۱:۰۸ ق.ظ
آخرین ارسال: marvelous
  بهترین منابع برای تحلیل اقتصادی کدامند؟ hoseyn9999so ۰ ۳۲۹ ۱۶ مهر ۱۳۹۸ ۰۶:۴۵ ق.ظ
آخرین ارسال: hoseyn9999so
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۴,۵۶۱ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20
  مرتبه مانی Sanazzz ۳ ۸۳۸ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۷۸۶ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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