انجمنصفحه اولجستجوی انجمن

[Masoud05]

(۱۷ بهمن ۱۳۹۳ ۰۴:۳۶ ب.ظ)me_pro نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

log*(n)=t درس بود

تو کتاب کرمن و قدسی راجع به این کلی توضیح داده. هر چند بطور مجانبی نمیشه گفت (O(1میشه اما چون برای مقادیر خیلی بزرگ عدد کوچکی میشه اونو از از مرتبه یه عدد ثابت فرض میکنن.

[ana9940]

(۱۷ بهمن ۱۳۹۳ ۰۴:۲۹ ب.ظ)Masoud05 نوشته شده توسط:  اگر درخت صرفا متوازن باشه هیچ کدوم در زمان log n حل نمیشه مگه اینکه صورت سوال رو بد گذاشته باشید!! مثلا برای مورد ۲ در یک درخت متوازن وقتی ندونیم ترتیب کلیدها چطوره عملا یک جستجو خطی نیاز داریم که مرتبه اون در بدترین حالت خطی است . مورد ۳ هم که مشخصه که مرتبه خطی داره.

صرفا متوازن نبود، یه فرض دیگه هم داشت.
هر گره ای مجموع فرزنداش رو داره.
این جوری حل میشه.

[me_pro]

(۱۷ بهمن ۱۳۹۳ ۰۴:۱۲ ب.ظ)sourena نوشته شده توسط:  من اصلا نمیدونم log* یعنی چی؟؟؟ :-D

تعریفی که من از یه سوالای پوران یادم بود تعداد باراهایی که از عدد n لوگ میگیریم تا به ۱ برسیم

[ziba.O]

سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)

[r3za]

(۱۷ بهمن ۱۳۹۳ ۰۵:۰۰ ب.ظ)ziba.O نوشته شده توسط:  سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)

فکر میکنم ۱۲ زدم

[me_pro]

(۱۷ بهمن ۱۳۹۳ ۰۵:۰۰ ب.ظ)ziba.O نوشته شده توسط:  سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)

من گفتم چون باید m اول باشه و اینگه هر چی بیشتر باشه احتمال برخورد کمتر میشه ۱۱ رو زدم نمیدونم درسته یا نه

[batouei]

(۱۷ بهمن ۱۳۹۳ ۰۵:۰۰ ب.ظ)ziba.O نوشته شده توسط:  سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)

میشه ۱۱///// من بقیه گزینه ها رو هم چک کردم.۱۱ از همه بهتر بود

[hosein70]

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

منم log* بدست اوردم

[archer22]

سوالی که گفته بود چند تا عدد میتونه pivot باشن جوابشو چی زدین؟

[maryam.roshan]

جواب سوال رابطه بازگشتی

[tex]T(n)=T(\log n) o(1)[/tex]

اگر در نظر بگیریم
[tex]n=2^k[/tex]

[tex]T(2^k)=T(\log2^k) o(1)[/tex]
[tex]W(k)=W(k) o(1)[/tex]
[tex]W=\theta(k)[/tex]
[tex]T(n)=\theta(\log n)[/tex]

---

سوال چه ارتباطی با این رابطه بازگشتی داره؟؟؟؟؟؟؟

[me_pro]

(۱۷ بهمن ۱۳۹۳ ۰۶:۴۲ ب.ظ)archer22 نوشته شده توسط:  سوالی که گفته بود چند تا عدد میتونه pivot باشن جوابشو چی زدین؟

۳ تا بود .. ۴ تاش سر جاشون بودن که یکی شون نمیتونس pivot بوده باشه

[artmiss]

(۱۷ بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)me_pro نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۶:۴۲ ب.ظ)archer22 نوشته شده توسط:  سوالی که گفته بود چند تا عدد میتونه pivot باشن جوابشو چی زدین؟

۳ تا بود .. ۴ تاش سر جاشون بودن که یکی شون نمیتونس pivot بوده باشه

سوال چی بود فک کنم سوالو بد خوندین
گزینه ها چی بودن؟

[archer22]

(۱۷ بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)me_pro نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۶:۴۲ ب.ظ)archer22 نوشته شده توسط:  سوالی که گفته بود چند تا عدد میتونه pivot باشن جوابشو چی زدین؟

۳ تا بود .. ۴ تاش سر جاشون بودن که یکی شون نمیتونس pivot بوده باشه

چرا یکیش نمیتونه پیوت باشه؟

[me_pro]

(۱۷ بهمن ۱۳۹۳ ۰۷:۰۴ ب.ظ)archer22 نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۶:۵۹ ب.ظ)me_pro نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۶:۴۲ ب.ظ)archer22 نوشته شده توسط:  سوالی که گفته بود چند تا عدد میتونه pivot باشن جوابشو چی زدین؟

۳ تا بود .. ۴ تاش سر جاشون بودن که یکی شون نمیتونس pivot بوده باشه

چرا یکیش نمیتونه پیوت باشه؟

چون وقتی pivot میشه بعدیاش ازش بزرگترن قبلیاش کوچیک تر (بعد پارتیشن) یکیش این خاصیت رو نداشت

[sntbrz]

(۱۷ بهمن ۱۳۹۳ ۰۵:۰۳ ب.ظ)me_pro نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۵:۰۰ ب.ظ)ziba.O نوشته شده توسط:  سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)

من گفتم چون باید m اول باشه و اینگه هر چی بیشتر باشه احتمال برخورد کمتر میشه ۱۱ رو زدم نمیدونم درسته یا نه

منم با این استدلال زدم ۱۱