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

مرتبه زمانی

ارسال:
  

rezajam پرسیده:

مرتبه زمانی

بچه ها کسی می تونه بگه چرا مرتبه زمانی این الگوریتم n میشه
for i to n do
for j to n do
{
;x=x+1
;n=n-1
}
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Hamid_0311 پاسخ داده:

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

با سلام دوست عزیز ببیند به ازای i=1 حلقه دوم n/2 اجرا میشه چرا؟ چون که به ازای هر بار اجرای حلقه دوم که همون j هستش یک دونه هم از n کم میشه یعنی توی هر بار اجرا عملا شرط داره دوتا دوتا کم میشه چون مقدار j داره یکی زیاد میشه و مقدار n هم داره یکی کم میشه پس بازه ی اجرای حلقه دوم داره از دو طرف کم میشه یعنی هم داره j زیاد میشه و هم n داره کم میشه ولی حلقه ی اول فقط داره n کم میشه ازش
پس وقتی حلقه دوم دیگه شرطش نقض بشه مقدار n تقریبا نصف شده پس برای اجرای i=2 مقدار n نصف شده است خوب حالا به ازای i=2
حلقه دوم این بار داره باز هم نصف میکنه مقدار n پس n/2/2 = n/4 میشه دیگه و به همین ترتیب هر دقعه مقدار داره تقسیم بر ۲ میشه پس جمع دنباله اینطوری میشه
n/2+n/4+n/8+n/16+....
خوب اگر از یک n فاکتور بگیریم میشه چی؟
۱/۲+۱/۴+۱/۸+۱/۱۶+....
خوب این یک سری هندسی نامتناهی که قدر نسبت اون ۱/۲ هست پس طبق قضیه سری ها داریم مجموع این میشه جمله اول تقسیم بر ۱-قدر نسبت
جمله اول که یک دوم هست صورت میشه ۱/۲ و مخرج هم میشه ۱-۱/۲ که میشه ۱/۲
۱/۲ تقسیم بر ۱/۲ میشه ۱
۱*N=n پس حاصل سری میشه n که میشه مرتبه خطی پس از مرتبه تتا n هستش

(ببخشید اگر یکم ریاضیاتشو بد نوشتم کلا این پرانتز مخرج این چیزا رو تو انجمن نمیشه خوب نوشت Big Grin )

امیدوارم متوجه شده باشید موفق باشیدBig Grin
نقل قول این ارسال در یک پاسخ

ارسال:
  

rezajam پاسخ داده:

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

یعنی موقعی که داره از n کم میشه این روی متغیر i تاثیر داره؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Hamid_0311 پاسخ داده:

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

من منظورتونو دقیقا از این سوال نفهمیدم ولی اگر منظورتون درست فهمیده باشم که منظورتون تاثیر n روی حلقه اول هست بله دیگه حلقه اول یعنی i تا کی اجرا میشه؟ تا وقتی که کوچکتر مساوی n باشه خوب متغیر n داره توی حلقه دوم هر بار که اجرا میشه یکی کم میشه یه بار فک کنم با یه عدد تریس کنید و توضیحاتی که دادمو بخونید متوجه شید کاملا
نقل قول این ارسال در یک پاسخ

ارسال:
  

rezajam پاسخ داده:

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

ببخشید فرض کنید به n=8 باشه در این صورت در حلقه دوم متغیر n تا عدد ۵ میره بعدش از حلقه خارج میشه سوال اصلی من اینه که آیا متغیر n که در حلقه اول هستش اونم برابر ۵ میشه یا نه؟ چرا متغیر n که در حلقه دوم هستش روی حلقه اول تاثیر داره؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Hamid_0311 پاسخ داده:

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

دوست عزیز ۸ فرض کنیم تا وقتی ۴ بشه اجرا میشه نه ۵ مقدار i کوچکتر مساوی n هست
بله تاثیر داره دیگه مشکل شما اینه برنامه نویسیتون ضعیفه کلا بچه های که برنامه نویسیشون ضعیفه بعضا سر این موضوعا قاطی می کنن
ببیند مقدار n توی یک جای ذخیره شده و هر دقعه که برنامه داره اجرا میشه این n خونده میشه از اون مکان 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