تالار گفتمان مانشت
روش یادگیری پیچیدگی زمانی ؟ - نسخه‌ی قابل چاپ

روش یادگیری پیچیدگی زمانی ؟ - elhameli - 06 خرداد ۱۳۹۱ ۰۳:۲۰ ب.ظ

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

با تشکر

RE: پیچیدگی زمانی ؟؟؟ - elhameli - 06 خرداد ۱۳۹۱ ۰۵:۵۱ ب.ظ

HuhHuhHuh

پیچیدگی زمانی ؟؟؟ - lsamimi - 07 خرداد ۱۳۹۱ ۰۹:۴۹ ق.ظ

در رابطه با پیچیدگی هر سوالی را با روش خاص خودش باید حل کنید
برای مثال اگر چند تا حلقه 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 بهتره شمارنده رو تشخیص بدید یا از روش عددگذاری استفاده کنید

پیچیدگی زمانی ؟؟؟ - Bache Mosbat - 07 خرداد ۱۳۹۱ ۰۱:۲۵ ب.ظ

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

پیچیدگی زمانی ؟؟؟ - sajad_8900 - 08 خرداد ۱۳۹۱ ۰۱:۵۴ ق.ظ

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

RE: پیچیدگی زمانی ؟؟؟ - enkido5 - 12 خرداد ۱۳۹۱ ۰۷:۵۳ ب.ظ

به نظر من به کتاب هورویتز و کتاب کورمن (CLRS) یه نگاهی بندازید.
نقل قول: یه جا از طریق عدد گذاری در سیگما رفته، لگاریتم، عدد گذاری در الگوریتم و یه جا هم از طریق ترکیب رفته....
در همه وارد هم سیگما جواب نمیده!!!
یه مسئله رو ممکنه از راه‌های متفاوتی بشه حل کرد. اگه مسئله مورد نظرتون رو بذارید بهتر میشه کمک کرد.

RE: روش یادگیری پیچیدگی زمانی ؟ - soheiy - 12 مهر ۱۳۹۱ ۰۱:۴۵ ب.ظ

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

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

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

روش یادگیری پیچیدگی زمانی ؟ - mrz_kamali - 02 آبان ۱۳۹۱ ۰۶:۴۶ ب.ظ

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

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

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

RE: روش یادگیری پیچیدگی زمانی ؟ - naderx - 02 آبان ۱۳۹۱ ۰۸:۳۵ ب.ظ

خوب به مفهوم فاکتوریل فکر کن
فاکتوریل 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
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی Tongue

RE: روش یادگیری پیچیدگی زمانی ؟ - javadem - 02 آبان ۱۳۹۱ ۰۹:۰۸ ب.ظ

(۰۲ آبان ۱۳۹۱ ۰۸:۳۵ ب.ظ)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
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی Tongue

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

(۰۲ آبان ۱۳۹۱ ۰۸:۳۵ ب.ظ)naderx نوشته شده توسط:  پس به این دلیل بدیهی ان به توان ان از فاکتوریل کوچکتره و این رابطه همیشه برقراره : !n > n به توان n
و اگر از دو طرف لگاریتم بگیریم به این نتیجه که شما میخواستی خواهیم رسید. به همین سادگی به همین خوشمزگی Tongue
البته این که شما میگید بدیهیه یعنی اگه از دو طرف لگاریتم بگیریم هنوز هم هم رشد نیستن؟ ([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] . فکر کنم این یکم معقولانه تر باشه نه؟

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

RE: روش یادگیری پیچیدگی زمانی ؟ - naderx - 02 آبان ۱۳۹۱ ۱۰:۰۷ ب.ظ

[/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]

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

RE: روش یادگیری پیچیدگی زمانی ؟ - javadem - 02 آبان ۱۳۹۱ ۱۰:۱۶ ب.ظ

(۰۲ آبان ۱۳۹۱ ۱۰:۰۷ ب.ظ)naderx نوشته شده توسط:  بله اینجوری میشه (ما نوکر شما هم هستیم قصد زدن تو ذوق شما رو نداشتم، تازه وقتی دکمه ارسال رو زدم دیدم شما زود تر جواب دادی و گرنه اگه میدیدم شما جواب دادین جسارت نمیکردمHeart)

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