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

سئوال از پیچیدگی

ارسال:
  

deledivouneh پرسیده:

سئوال از پیچیدگی

من نمیدونم برا چیه که خیلی به این پیچیدگی‌ها گیر دادم.این پیچیدگی رو کسی حل کرده؟؟


T(n)=T(n/2+√n)+1

۰
ارسال:
  

- rasool - پاسخ داده:

پیچیدگی

فکر می کنم اینطوری بشه:

چون (T(n یک تابع اکیدا صعودی است پس برای n های به اندازه کافی بزرگ داریم:

[tex]T(\frac{n}{2})<T(\frac{n}{2} \sqrt{n})<T(\frac{3n}{4})\Rightarrow T(\frac{n}{2}) 1<T(\frac{n}{2} \sqrt{n}) 1<T(\frac{3n}{4}) 1[/tex]


حالا اگه مرتبه‌ی اون عبارت سمت راست نامساوی رو حل کنیم با قضیه اصلی می شه‌: Logn

پس مرتبه‌ی عبارت وسطی نامساوی‌، که مد نظر ما هم هست‌: می شه‌ SadO(Logn



یک جورایی هم قضیه ساندویچ خودشو توی این سوال نشون می ده. فتدبر!

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: پیچیدگی

من هم جواب رو تتای n آوردم لطفا دوستان در مورد درستی حلم نظر بدن

[tex]T(n)=T(\frac{n}{2} \sqrt{n}) 1\rightarrow T(\frac{n}{\sqrt{n}})=T(\frac{n}{2\sqrt{n}} 1) 1\rightarrow H(m)=H(\frac{m}{2}) 1\rightarrow \theta (lgm)=\theta(lg\frac{n}{\sqrt{n}})=\theta(lgn)[/tex]

۰
ارسال:
  

deledivouneh پاسخ داده:

RE: پیچیدگی

مرسی بچه‌ها .
من خودم این راه حل رو دارم.درسته به نظرتون؟


فایل‌(های) پیوست شده
P1.docx
اندازه فایل: ۱۶/۸۳ KB



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۷۸۲ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۹۱۶ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
  مشکل در پیچیدگی زمانی ماهی ۲۵۸ ۲ ۳,۰۰۹ ۲۳ تیر ۱۳۹۷ ۱۲:۱۸ ق.ظ
آخرین ارسال: Alisalar
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۷,۴۷۰ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi
  پیچیدگی زمانی مرتب سازی حبابی در حالت متوسط arman12345 ۲ ۲,۴۱۱ ۳۰ بهمن ۱۳۹۶ ۰۶:۰۶ ب.ظ
آخرین ارسال: arman12345
  پیچیدگی زمانی ماشین های پذیرنده و زبانها Sepideh96 ۰ ۱,۴۴۴ ۲۸ آذر ۱۳۹۶ ۰۳:۳۷ ق.ظ
آخرین ارسال: Sepideh96
  پیچیدگی زمانی Alirezaj ۰ ۱,۳۶۹ ۰۷ آذر ۱۳۹۶ ۱۰:۰۶ ق.ظ
آخرین ارسال: Alirezaj
  محاسبه پیچیدگی گیت mo_mohamad ۱ ۱,۹۳۹ ۰۸ شهریور ۱۳۹۶ ۱۱:۰۷ ب.ظ
آخرین ارسال: BBumir
  محاسبه پیچیدگی گیت mo_mohamad ۰ ۱,۳۸۲ ۰۵ شهریور ۱۳۹۶ ۰۹:۳۲ ب.ظ
آخرین ارسال: mo_mohamad
  دو سئوال طراحی الگوریتم java50 ۱ ۱,۶۷۸ ۱۱ اسفند ۱۳۹۵ ۰۱:۱۲ ق.ظ
آخرین ارسال: alireza01

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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