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

مرتبه زمانی تک برنامه

ارسال:
  

Doctorwho پرسیده:

مرتبه زمانی تک برنامه

با عرض سلام و خسته نباشیید

من یه سوال داشتم میخواستم اگه امکانش هست ابتدا یک توضیحی در مورد اینکه باید چطوری مرتبه ی زمانی یک تک کد رو به دست بیاریم بدهید و بعدم مرحله به مرحله و توضیح فاری و تشریحی کامل توضیح بدهید چوری این مرتبه ی زمانی این تک کدها ها رو به دست آوریم , و در اخر هم اگه راه حل کوتاه تری یا تستی سراغ دارید بفرمایید باتشکر SmileSmileSmile

کدها در پیوست قرار دارند.Smile


فایل‌(های) پیوست شده
file.txt
اندازه فایل: ۳۷۱ bytes
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

azk84 پاسخ داده:

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

راه حل خاصی نداره، باید تحلیل کنین ببینین واقعاً حلقه‌هاتون چند بار اجرا میشن!

مثلاً در مورد دومی، برای همون دور اول اجرای حلقه‌ی بیرونی (یعنی برای i=1) به دلیل صفر شدن n در حلقه‌ی داخلی دیگه حلقه بیرونی اجرا نمیشه. به عبارت دیگه حلقه‌ی بیرونی تنها یک بار اجرا میشه کلاً. در حلقه داخلی هم با هر بار افزایش j مقدار n کاهش پیدا می‌کنه و تا زمانی که مقدار هر دوتاشون برابر بشه (در نقطه‌ی n0/2)، در نتیجه این حلقه هم n/2 بار اجرا میشه. پس کل دفعات اجرای x = x + 1 برابره با n/2 در در نتیجه مرتبه‌ی تکه کد دوم میشه [tex]\Theta(n)[/tex].

در مورد تکه کد اولی هم تعداد دفعات اجرای حلقه‌ی بیرونی با همون استدلال n/2 هستش. بنابراین با n ارتباط خطی داره. تعداد دفعات اجرای حلقه داخلی هم با کم شدن n هر بار کم میشه، ولی همیشه بین n (در ابتدا) و n/2 (در پایان) قرار داره، بنابراین این هم ارتباط خطی با n داره. پس کل دفعات اجرای x = x + 1 برابر با ضریبی از [tex]n^{2}[/tex] میشه و در نتیجه مرتبه‌ی کل کد [tex]\Theta(n^{2})[/tex] هستش.

در مورد تعداد دفعات اجرای x = x+1 (و در نتیجه مرتبه‌کل کد) در کد سوم، اینطوری بررسی می‌کنیم که برای i = 1 حلقه‌ی داخلی (و در نتیجه کد x = x+1) به تعداد n بار اجرا میشه. برای i = 2 حلقه‌ی داخلی n/2 بار اجرا میشه. برای i = 3 حلقه‌ی داخلی n/3 بار اجرا میشه و... .
بنابراین کل دفعات اجرای کد x = x + 1 (و مرتبه‌ی کد سوم) برابره با:
[tex]n \frac{n}{2} \frac{n}{3} \frac{n}{4} ...=n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ...)=\Theta(n\cdot log(n))[/tex]
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کمک برای شروع برنامه نویسی seyed ehsn ۲۱ ۱۵,۹۷۷ ۲۴ بهمن ۱۴۰۲ ۰۵:۱۰ ب.ظ
آخرین ارسال: maryamjafari63
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۸۹۶ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  رودمپی برای برنامه نویسی Doctorwho ۱ ۲,۱۱۸ ۲۵ آذر ۱۴۰۰ ۰۳:۰۲ ق.ظ
آخرین ارسال: one hacker alone
  استخدام برنامه نویس یا کارآموز برنامه نویسی سی شارپ Hesitant_Girl ۰ ۱,۷۹۱ ۲۰ شهریور ۱۴۰۰ ۱۲:۰۲ ب.ظ
آخرین ارسال: Hesitant_Girl
  رودمپی برای یادگیری برنامه نویسی Doctorwho ۰ ۱,۸۱۸ ۲۳ اردیبهشت ۱۴۰۰ ۱۱:۲۲ ق.ظ
آخرین ارسال: Doctorwho
  درخواست برنامه برای اردینو در iot seokheiry ۱ ۳,۳۷۰ ۱۳ بهمن ۱۳۹۹ ۱۲:۵۵ ب.ظ
آخرین ارسال: iot-programer
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۷۶ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۳۵ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  کدام زبان برنامه‌نویسی بهترین انتخاب است؟ elecomco ۲ ۳,۱۳۱ ۱۰ شهریور ۱۳۹۹ ۰۵:۱۶ ب.ظ
آخرین ارسال: kilookiloo
Sad مشکل در برنامه نویسی شیء گرا Xialu ۰ ۲,۲۸۸ ۰۵ شهریور ۱۳۹۹ ۱۲:۰۰ ب.ظ
آخرین ارسال: Xialu

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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