برای پیچیدگی باید زیاد مسئله ببینین همین .

سلام دوست عزیز.
یه نگاهی به فصل اول کتاب ساختمان داده استاد هورویتز بنداز.گفته چیارو حساب کنی چیارو حساب نکنی.فک کنم به دردت بخوره.

به نظر من به کتاب هورویتز و کتاب کورمن (CLRS) یه نگاهی بندازید.

نقل قول: یه جا از طریق عدد گذاری در سیگما رفته، لگاریتم، عدد گذاری در الگوریتم و یه جا هم از طریق ترکیب رفته....
در همه وارد هم سیگما جواب نمیده!!!

یه مسئله رو ممکنه از راه‌های متفاوتی بشه حل کرد. اگه مسئله مورد نظرتون رو بذارید بهتر میشه کمک کرد.

(۰۶ خرداد ۱۳۹۱ ۰۳:۲۰ ب.ظ)elhameli نوشته شده توسط:  سلام به همه دوستان
لطفا منو راهنمایی کنید، من کتاب تست مقسمی و طراحی الگوریتم پوران و یکم گریمالدی در مورد پیچیدگی زمانی خوندم، کلا قاطی کردم.من نمی دونم از کجا باید بفهمم تعداد دفعات اجرای یک خط کد در یک الگوریتم رو از چه راه حلی باید بدست بیارم!!!
یه جا از طریق عدد گذاری در سیگما رفته، لگاریتم، عدد گذاری در الگوریتم و یه جا هم از طریق ترکیب رفته....
در همه وارد هم سیگما جواب نمیده!!!
میخواستم بدونم راه اساسی برای حل همه این الگوریتم ها چی هست ؟ هر کدوم راه حل جداگانه باید برم ؟ از کجا باید بفهمم برای هر کدوم از چه راه حلی باید برم ؟
کتابی در این موضوع هست؟؟ که خوب توضیح داده باشه، تا از پس هر نوع الگوریتمی بر بیام !!!
لطفا یه راه حل اساسی بهم نشون بدین...

با تشکر

______________________________________________________________________
راه حلش حل تست و تست و تست و تمرین . .
من به این نتیجه رسیدم. خودمم خیلی مشکل دارم. منتها سعی کن تست هارو مجددا بزنی . کتاب ساختمان داده پوران خوبه

اکه میشد اینجا تست های نکته دارو بررسی میکردیم خوب بود

سلام خسته نباشید . اثبات این قضیه رو می خواستم کسی هست که بتونه جواب بده ؟
nlog n
عضو
logn!

---

البته عضو O بزرگ هستش

---

N log n ε (log n!)
خواهش می کنم کمکم کنید

خوب به مفهوم فاکتوریل فکر کن
فاکتوریل n یعنی چی ؟ یعنی n*n-1*n-2*n-3...*3*2*1
به نظرت این رو میشه تقریبا بگیریم ان تا ان که در هم ضرب شدن ؟ n*n*n*n*...*n*n*n*n
ٱره میشه گرفت ولی قبول داری اگر ان به توان ان رو بگیریم فاکتوریل ، انگار یه مقدار کوچیک رو با یه مقدار بزرگ جانشین کردیم ؟ چون قبلا بود n*n-1*n-2*n-3...*3*2*1 و حالا شده : n*n*n*n*...*n*n*n*n
پس به این دلیل بدیهی ان به توان ان از فاکتوریل کوچکتره و این رابطه همیشه برقراره : !n > n به توان n
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی

(۰۲ آبان ۱۳۹۱ ۰۸:۳۵ ب.ظ)naderx نوشته شده توسط:  خوب به مفهوم فاکتوریل فکر کن
فاکتوریل n یعنی چی ؟ یعنی n*n-1*n-2*n-3...*3*2*1
به نظرت این رو میشه تقریبا بگیریم ان تا ان که در هم ضرب شدن ؟ n*n*n*n*...*n*n*n*n
ٱره میشه گرفت ولی قبول داری اگر ان به توان ان رو بگیریم فاکتوریل ، انگار یه مقدار کوچیک رو با یه مقدار بزرگ جانشین کردیم ؟ چون قبلا بود n*n-1*n-2*n-3...*3*2*1 و حالا شده : n*n*n*n*...*n*n*n*n
پس به این دلیل بدیهی ان به توان ان از فاکتوریل کوچکتره و این رابطه همیشه برقراره : !n > n به توان n
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی

آره درست میگید، من گفتم شاید بشه به این صورت هم n! را نوشت :
[tex]n * (n-1)*(n-2)*...(n-n 2)*(n-n 1)[/tex]
و از ضرب این جمله ها در هم یه چند جمله ای درجه n به دست میاد که البته کم توجهی کردم. گویا اشتباه کردم. الان که بیشتر توجه میکنم اشتباهم خیلی شدیده. اما یهو ای تو ذهنم فوران کرد. اما شما این فوران بزرگ علمی رو خفه کردید.

(۰۲ آبان ۱۳۹۱ ۰۸:۳۵ ب.ظ)naderx نوشته شده توسط:  پس به این دلیل بدیهی ان به توان ان از فاکتوریل کوچکتره و این رابطه همیشه برقراره : !n > n به توان n
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی

البته این که شما میگید بدیهیه یعنی اگه از دو طرف لگاریتم بگیریم هنوز هم هم رشد نیستن؟ ([tex]log(n!)[/tex] و [tex]log(n^n)[/tex])
آخه این هم رشدی رو توی کتاب پوران فقط گفته.
من تو اثبات اشتباه کردم اما فکر میکنم همچین رابطه ای بر قرار باشه

نمیشه اینطور ثابت کرد؟
[tex]log(n!)[/tex] = [tex]log(n * (n-1) * ( n-2) ... *2* 1)[/tex]که اینم برابره با [tex]log(n) log(n-1) log(n-2) ... log(2) log(1)[/tex] و از اونجایی که در کتاب ثابت شده همه این لگاریتم ها که با هم جمع شدن هم رشد هستند که در نتیجه همه رو [tex]log(n)[/tex] در نظر میگیریم که جمعشون میشه [tex]nlogn[/tex] . فکر کنم این یکم معقولانه تر باشه نه؟

دیگه تو ذوقم نزن باشه؟؟؟