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

ساختمان داده-مرتبه زمانی صفحه ۱۵ کتاب پوران

ارسال:
  

Mahand پرسیده:

ساختمان داده-مرتبه زمانی صفحه ۱۵ کتاب پوران

سلام دوستان
میشه این سوال ها رو با راه حل،حلشون کنید؟

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

۱
ارسال:
  

Pure Liveliness پاسخ داده:

RE: ساختمان داده-مرتبه زمانی صفحه ۱۵ کتاب پوران

(۰۸ آبان ۱۳۹۵ ۱۲:۱۷ ب.ظ)Flora نوشته شده توسط:  سلام دوستان
میشه این سوال ها رو با راه حل،حلشون کنید؟

سلام

در اولی، اون حالت‌های خاص که در نظر گرفته نمی‌شوند. اصلش حلقه هست. در حلقه هم ممکن هست همون اولش، یعنی به ازای i=3، باقی‌مونده‌ی n به i صفر بشه، مثلاً n=90000000 باشه. ولی باز بدترین حالت باید در نظر گرفت بشه. برای اینکه [tex]i^2<n[/tex] باشه، i باید [tex]\sqrt{n}[/tex] تا جلو بره. البته چون اینجا i = i + 2 میشه، باید [tex]\frac{\sqrt{n}}{2}[/tex] جلو بره که مهم نیست و مرتبه‌شون همون [tex]\theta(\sqrt{n})[/tex] هست. دقیق‌ترش میشه [tex]\frac{\sqrt{n}}{2}-3[/tex] چون اولش از ۳ شروع می‌شه (و ۳ گام رفته جلو).

دومی هم باز راحت هست چون حلقه‌ی داخلی، مستقل از حلقه‌ی بیرونی هست. یعنی j هر بار تا n میره (به جای اینکه مثلاً تا i بره که نیاز به سیگما یا روش‌های دیگه باشه). متغیر i هر بار ضربدر ۲ میشه تا وقتی که به n برسه، پس میشه [tex]\log(n)[/tex] بار. j هم که هر بار از ۱ تا n میره، پس مرتبه‌ی کلی میشه [tex]n\cdot\log(n)[/tex]. اگر متغیر حلقه‌ی داخلی به متغیر حلقه‌ی بیرونی ربط داشت (مثلا j هر بار تا i می‌رفت) نمیشد به این راحتی ضرب کرد و باید از سیگما استفاده بشه مثلاً.

در سومی هم متغیر حلقه‌ها مستقل هستند، اولی n تا گام داره و دومی [tex]\log(n)[/tex] تا. یعنی به ازای هر i، دومی [tex]\log(n)[/tex] تا دستور اجرا می‌کنه. بنابراین مرتبه مثل بالایی میشه [tex]n\cdot\log(n)[/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Mahand پاسخ داده:

RE: ساختمان داده-مرتبه زمانی صفحه ۱۵ کتاب پوران

ممنون.
ببخشید حلقه اول رو میشه بیشتر توضیح بدین؟
چرا میشه از مرتبه [tex]\sqrt{n}[/tex]
نقل قول این ارسال در یک پاسخ

ارسال:
  

Pure Liveliness پاسخ داده:

RE: ساختمان داده-مرتبه زمانی صفحه ۱۵ کتاب پوران

(۰۸ آبان ۱۳۹۵ ۰۱:۳۱ ب.ظ)Flora نوشته شده توسط:  ممنون.
ببخشید حلقه اول رو میشه بیشتر توضیح بدین؟
چرا میشه از مرتبه [tex]\sqrt{n}[/tex]
خواهش میکنم.
i از ۳ شروع میشه. اگه از اون دو تا دستور صرف نظر کنیم و بدترین حالت رو در نظر بگیریم که تا زمانی که [tex]i^2[/tex] از n کوچیکتر هست حداقل اون دو تا دستور اول اجرا نشه. یعنی حلقه ی while رو بررسی میکنیم.
اولش i=3
[tex]i^2<n[/tex] فرض میکنیم که else اجرا بشه تا حد امکان. (باز بدترین حالت رو در نظر میگیریم، دقت بشه توی سوالات باید به نکات دیگه ای هم توجه کنیم گاهاََ)
i+=2 پس i میشه ۵
حالا ۲۵ رو با n مقایسه میکنه.
دفعه ی بعد i=7 و ۴۹ با n مقایسه میشه.
یعنی هر بار [tex](3+2k)^2[/tex] با n مقایسه میشه.
دفعه ی اول [tex]i^2=(3+2\cdot1)^2[/tex]
دفعه ی دوم [tex]i^2=(3+2\cdot2)^2[/tex]
دفعه ی سوم [tex]i^2=(3+2\cdot3)^2[/tex]
.
.
دفعه ی k ام [tex]i^2=(3+2\cdot k)^2[/tex]
تا زمانی که [tex]i^2<=n[/tex]
یعنی باید k رو به دست بیاریم. رابطه رو داریم که بعد از k بار چه اتفاقی میفته. حالا اون مقدار[tex]i^2=(3+2\cdot k)^2[/tex] باید کوچیکتر مساوی n باشه دیگه.
k میشه:
[tex]i^2=(3+2k)^2<=\: n\: \: \: \: \longrightarrow\: \: \: 9+4k^2+12k\: =\theta(k^2)<=\: n\: \: \longrightarrow\: k<=\sqrt{n}[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Mahand پاسخ داده:

RE: ساختمان داده-مرتبه زمانی صفحه ۱۵ کتاب پوران

(۰۸ آبان ۱۳۹۵ ۰۷:۰۹ ب.ظ)Pure Liveliness نوشته شده توسط:  
(08 آبان ۱۳۹۵ ۰۱:۳۱ ب.ظ)Flora نوشته شده توسط:  ممنون.
ببخشید حلقه اول رو میشه بیشتر توضیح بدین؟
چرا میشه از مرتبه [tex]\sqrt{n}[/tex]
خواهش میکنم.
i از ۳ شروع میشه. اگه از اون دو تا دستور صرف نظر کنیم و بدترین حالت رو در نظر بگیریم که تا زمانی که [tex]i^2[/tex] از n کوچیکتر هست حداقل اون دو تا دستور اول اجرا نشه. یعنی حلقه ی while رو بررسی میکنیم.
اولش i=3
...
عالی بود.
خییییلی ممنونم.
Pure Liveliness، در تاریخ ۰۸ آبان ۱۳۹۵ ۱۰:۱۰ ب.ظ برای این مطلب یک پانوشت گذاشته است:

خواهش میکنم Smile

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۲,۵۷۴ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۱,۲۵۹ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  سوال در مورد صفحه بندی در سیستم عامل Azadam ۱ ۱,۸۳۱ ۱۳ دى ۱۴۰۰ ۱۱:۰۴ ق.ظ
آخرین ارسال: Azadam
  درخواست حل المسائل کتاب پایگاه داده پیشرفته سیلبرشاتس shahryar711 ۲ ۶,۳۲۱ ۲۲ آذر ۱۳۹۹ ۰۱:۲۷ ب.ظ
آخرین ارسال: zhila1994
  درخواست اپلود کتاب یا لینک دانلود کتاب+معرفی سایت دانلود کتاب ریحانه ۱۲۹ ۸۲,۶۱۳ ۱۱ آذر ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: Ariana2020
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۶۶۰ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf
  صفحه چند سطحی Flash1 ۰ ۱,۷۷۹ ۱۰ تیر ۱۳۹۹ ۰۵:۵۸ ب.ظ
آخرین ارسال: Flash1
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۴,۵۲۸ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۷۸۶ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۹,۹۸۲ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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