تالار گفتمان مانشت

سلام به همه دوستان
لطفا منو راهنمایی کنید، من کتاب تست مقسمی و طراحی الگوریتم پوران و یکم گریمالدی در مورد پیچیدگی زمانی خوندم، کلا قاطی کردم.من نمی دونم از کجا باید بفهمم تعداد دفعات اجرای یک خط کد در یک الگوریتم رو از چه راه حلی باید بدست بیارم!!!
یه جا از طریق عدد گذاری در سیگما رفته، لگاریتم، عدد گذاری در الگوریتم و یه جا هم از طریق ترکیب رفته....
در همه وارد هم سیگما جواب نمیده!!!
میخواستم بدونم راه اساسی برای حل همه این الگوریتم ها چی هست ؟ هر کدوم راه حل جداگانه باید برم ؟ از کجا باید بفهمم برای هر کدوم از چه راه حلی باید برم ؟
کتابی در این موضوع هست؟؟ که خوب توضیح داده باشه، تا از پس هر نوع الگوریتمی بر بیام !!!
لطفا یه راه حل اساسی بهم نشون بدین...

با تشکر

در رابطه با پیچیدگی هر سوالی را با روش خاص خودش باید حل کنید
برای مثال اگر چند تا حلقه for داشته باشی که شمارنده های حلقه ها هیچ وابستگی به هم نداشته باشند نیازی نیست از سیگما استفاده کنی(البته از سیگما هم می تونه حل بشه) کافیه تعداد اجرای حلقه ها رو از طریق کرانهای بالا و پایین محاسبه کنی. برای مثال در کد زیر:
for i=1 to n do
for j=1 to m do
x=x+1
دستور سوم nm بار تکرار میشه چون for اول n-1+1 (کران بالا منهای کران پایین بعلاوه یک) و for دوم هم m-1+1 بار اجرا میشه و اینها در هم ضرب میشوند.
اما در جاهایی که شمارنده های حلقه بهم وابسته هستند راحتتره که از روش سیگما استفاده کنی
for i=1 to n do
for j=1 to i do
x=x+1
در این حالت شمارنده j به i وابسته هست وداریم:
[tex]\sum_{i=1}^{n} \sum_{j=1}^{i}1[/tex]
در رابطه با حلقه های while بهتره شمارنده رو تشخیص بدید یا از روش عددگذاری استفاده کنید

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

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

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

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

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

(06 خرداد 1391 03:20 ب.ظ)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
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی

(02 آبان 1391 08:35 ب.ظ)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 به دست میاد که البته کم توجهی کردم. گویا اشتباه کردم. الان که بیشتر توجه میکنم اشتباهم خیلی شدیده. اما یهو ای تو ذهنم فوران کرد. اما شما این فوران بزرگ علمی رو خفه کردید.

(02 آبان 1391 08:35 ب.ظ)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] . فکر کنم این یکم معقولانه تر باشه نه؟

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

[/quote]

نمیشه اینطور ثابت کرد؟
[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] . فکر کنم این یکم معقولانه تر باشه نه؟

دیگه تو ذوقم نزن باشه؟؟؟
[/quote]

بله اینجوری میشه (ما نوکر شما هم هستیم قصد زدن تو ذوق شما رو نداشتم، تازه وقتی دکمه ارسال رو زدم دیدم شما زود تر جواب دادی و گرنه اگه میدیدم شما جواب دادین جسارت نمیکردم)

(02 آبان 1391 10:07 ب.ظ)naderx نوشته شده توسط: [ -> ]بله اینجوری میشه (ما نوکر شما هم هستیم قصد زدن تو ذوق شما رو نداشتم، تازه وقتی دکمه ارسال رو زدم دیدم شما زود تر جواب دادی و گرنه اگه میدیدم شما جواب دادین جسارت نمیکردم)

سالاری داداش آخه اون اولیه خیلی تابلو بود. روی چیزای بدیهی به خاطر کم توجهی اشتباه میکنم، خدا کنه سر کنکور از این اشتباها نکنم.
خیلی ممنون که این دفعه تو ذوقم نزدید!!!!