نمایش نتایج 1 تا 11 از 11

نام تاپیک: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

  1. #1

    چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    من برنامه ی سری فیبوناچی را به دو صورت بازگشتی و ساده نوشتم.
    از راه بازگشتی برای عدد 50 حدود 3 دقیقه و ۳۹ ثانیه طول کشید
    از راه غیربازگشتی برای عدد 50 کمتر از یک میلی ثانیه طول کشید.

    میخواستم ببینم علت چیست؟ و چگونه میتوانم تابع زمانی مربوط به الگوریتم های بازگشتی و غیربازشتی این مسئله را بدست آورم؟

    import java.util.Calendar;
    /**
    *
    * @author milad
    */
    public class Recursive {


    public static long recursiveFibonacci( long n ) {
    if ( n == 0 || n == 1 ) {
    return n;
    } else {
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
    }
    }
    public static long fibonacci( long n ) {
    if ( n == 0 ) {
    return 0;
    }
    if ( n == 1) {
    return 1;
    }
    long a = 0;
    long b = 1;
    long c;
    while ( n > 1 ) {
    c = a + b;
    a = b;
    b = c;
    n--;
    }
    return b;
    }

    public static void main(String[] args) {
    System.out.println(System.currentTimeMillis());
    System.out.println(fact.recursiveFactorial(5));
    System.out.println(System.currentTimeMillis());
    System.out.println(fibonacci(50));
    System.out.println(System.currentTimeMillis());
    }

    }

  2. #2
    کاربر دائمی آواتار manager
    تاریخ عضویت
    شهریور 1384
    محل زندگی
    Z
    سن
    38
    پست
    771

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    اول اینکه این کار شما (زمانگیری کردن الگوریتم) اساسا اشتباه و غلطه، و مبنای ارزیابی هیچ الگوریتمی نیست. دوم اینکه شما می تونید با مراجعه به مباحث ارزیابی الگوریتم ها خصوصا الگوریتم های تقسیم و غلبه و یا مراجعه به ریاضیات گسسته بخش حل روابط بازگشتی با نحوه حل اینگونه مسائل آشنا بشید.

  3. #3

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    مگه شما وقتی برای عددهای بزرگ تر از 2 زمانی که می خوای محسابه کنی عدد n-1 بعلاوه n-2 رو return نمی کنی؟ خب پس در واقع برای حالتی که n=1 , 2باشه مرته زمانی شما 1 هست و برای بزرگ تر از 2 این میشه a(n-1)+ a(n-2)+1حالا اگه لین رو حساب کنی به صورت بازگشتی جواب بر حسب n به دست می یاد

  4. #4

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    نقل قول نوشته شده توسط manager مشاهده تاپیک
    اول اینکه این کار شما (زمانگیری کردن الگوریتم) اساسا اشتباه و غلطه، و مبنای ارزیابی هیچ الگوریتمی نیست. دوم اینکه شما می تونید با مراجعه به مباحث ارزیابی الگوریتم ها خصوصا الگوریتم های تقسیم و غلبه و یا مراجعه به ریاضیات گسسته بخش حل روابط بازگشتی با نحوه حل اینگونه مسائل آشنا بشید.
    میشه بگید چجوری باید الگوریتمم را زمانگیری کنم؟
    در مورد تقسیم و غلبه بیشتر مطالعه می کنم.
    تشکر

  5. #5
    کاربر دائمی آواتار manager
    تاریخ عضویت
    شهریور 1384
    محل زندگی
    Z
    سن
    38
    پست
    771

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    نباید الگوریتم رو زمانبندی کنی ، شما باید یه تخمینی از زمان مصرفی بر حسب ورودی های الگوریتم بدست بیاری، یا بگی مثلا فلان دستور الگوریتم اینقدر بار تکرار می شه. مثلا آیا می تونم بگم این الگوریتم زمان مصرفیش 20 ثانیه ست !!! خوب 20 ثانبه رو چه دستگاهی ؟ رو چه سیستم عاملی ؟ رو چه CPU یا مادربردی ؟ رو سرور یا رو مبایل ؟!!
    به فصل اول هر کتاب طراحی الگوریتمی نگاه کنی کامل توضیح داده شده.
    آخرین ویرایش به وسیله manager : پنج شنبه 15 اسفند 1387 در 16:23 عصر

  6. #6

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    نقل قول نوشته شده توسط manager مشاهده تاپیک
    نباید الگوریتم رو زمانبندی کنی ، شما باید یه تخمینی از زمان مصرفی بر حسب ورودی های الگوریتم بدست بیاری، یا بگی مثلا فلان دستور الگوریتم اینقدر بار تکرار می شه. مثلا آیا می تونم بگم این الگوریتم زمان مصرفیش 20 ثانیه ست !!! خوب 20 ثانبه رو چه دستگاهی ؟ رو چه سیستم عاملی ؟ رو چه CPU یا مادربردی ؟ رو سرور یا رو مبایل ؟!!
    به فصل اول هر کتاب طراحی الگوریتمی نگاه کنی کامل توضیح داده شده.
    خانم/آقای محترم اگر دقت کرده باشید من هیچگاه نگفتم زمان مصرفی این الگوریتم ۲۰ ثانیه یا ۱۰ ثانیه است. بلکه تنها دو الگوریتم بازگشتی و غیربازگشتی را روی سیستم خودم مقایسه کرده‌ام
    و مطمئنا این اعداد و ارقام برای ورودی های دیگر و هچنیین برای شرایط دیگر متفاوت خواهد بود.

    اصل سوال من هم همین بود که شما چندان کمکی به من نکردید. یعنی من تابعی میخوام پیدا کنم که بر اساس وردی‌ها و پارامترهای دیگر بتوانم پیچیدگی زمان این الگوریتم را پیدا کنم.
    البته باز هم به خاط ‍«کلمات کلیدی» که به من تقدیم نمودید متشکر. جست و جو می‌کنم.

    از دوستان دیگر کسی نمیتونه منو بیشتر راهنمایی کنه؟

  7. #7

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    میشه بگید چجوری باید الگوریتمم را زمانگیری کنم؟
    در مورد تقسیم و غلبه بیشتر مطالعه می کنم.
    تشکر
    برای محاسبه ی پیچیدگی زمانی یک الگوریتم زمان و ثانیه رو در نظر نمیگیرن. شما باید هر دستور رو "یک واحد زمانی" (توجه کنید بر حسب ثانیه نیست فقط یک معیار اندازه گیری بدون واحد) در نظر بگیرید و سپس حساب کنید توی بدترین حالت داده های ورودی یعنی حالتی که دستورات بیشترین تعداد اجرا رو داشته باشند هر دستور چند باز اجرا میشه و ارزش زمانی هر دستور رو یک واحد حساب کنید. بعد یه تابع بدست میاد که یا یک عدد ثابته یا درجه n، نمایی لگاریتمی و ... که بهش میگن تابع پیچیدگی زمانی الگوریتم یا (Big Oh) و معیار اصلی سنجش کارایی یک الگوریتمه. معمولا دستوراتی مثل حلقه های تکرار، بازگشتی، پرش های شرطی و ... که در اونها تعداد تکرار دستورات متغیره باعث میشن که تابع از نوع درجه 1،2 ...n لگاریتمی، نمایی و ... در بیان در غیز اینصورت اگه تعداد تکرار هر دستور فقط 1 بار باشه اگه 1000 خط کد هم داشته باشیم باز پیچیدگی زمانی اون برابر (O(1 در میاد. میدونم کامل متوجه نشدین ولی تا یک کتاب ساختمان داده رو نخونین روش دقیق محاسبه پیچیدگی زمانی یک الگوریتم رو متوجه نمیشین. البته تو الگوریتم های متداولی که توی دروس دانشگاهی باهاشون سرو کار دارین مثل فیبوناچی کار پیچیده ای نیست
    آخرین ویرایش به وسیله Shadow Dancer : پنج شنبه 15 اسفند 1387 در 19:58 عصر

  8. #8
    VIP آواتار xxxxx_xxxxx
    تاریخ عضویت
    شهریور 1386
    محل زندگی
    X place
    سن
    34
    پست
    4,768

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    میخواستم ببینم علت چیست؟
    علت كه كاملاً روشن هست.
    وقتي از روش بازگشتي برنامه اجرا ميشه. در هربار اجرا اين تابع دو بار خودش رو اجرا مي كنه. شما درختش رو رسم كنيد ببينيد چقدر وحشتناك ميشه. يعني 2 به توان 50 بار. حالا 50 نه 48 به خاطر معلوم بودن مقادير مرزي. يعني بيش از 650 هزار ميليارد بار اين تابع اجرا ميشه.
    ولي تو محاسبه اين سري با يك حلقه ساده تنها 50 بار (48 بار) دستور اصلي تابع اجرا ميشه.
    -----
    در مورد محاسبه سرعت(زمان) در الگوريتم، شما اجراي هر دستور رو 1 در نظر بگيريد. اونوقت ببينيد در هر دو حالت چقدر زمان ميبره يا چند دستور اجرا ميشه تا تابع به انتها ميرسه.
    آخرین ویرایش به وسیله xxxxx_xxxxx : جمعه 16 اسفند 1387 در 12:25 عصر
    الگوریتم هایی که تاریخچه خود را فراموش می کنند، محکوم به تکرار آن هستند.

  9. #9
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    زمان مصرفی تابع فیبوناتچی برای حالت بازگشتی بصورت نمایی و از مرتبه
    O(1.6^n)
    و برای حالت بازگشتی خطی و از مرتبه
    O(n)
    مبیاشد. البته میشه اینکار رو در زمان
    O(log n)
    در حالت تکراری بدست آورد که اگه خواستید کدش رو براتون مینویسم.
    دلیلش رو هم که دوست خوبمون XXXX مطرح کرد. ولی تبدیل الگوریتمهای بازگشتی به تکراری عالمی داره که تو فیبوناتچی نمود پیدا کرده. حتی قسمتی از quick sort رو هم میتوان به صورت تکراری تبدیل کرد. (کلا الگوریتمهایی بازگشتی با ویژگی خاص رو میشه به تکراری تبدیل کرد)

  10. #10
    کاربر دائمی آواتار el_abdollahi
    تاریخ عضویت
    شهریور 1385
    محل زندگی
    شهر قنات و قنوت و قناعت
    پست
    476

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    با سلام
    میشه الگوریتم فیبوناچی با مرتبه log(n) رو بگین؟

    ممنون.

  11. #11
    کاربر دائمی آواتار pesar irooni
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    تهران
    سن
    40
    پست
    495

    نقل قول: چگونه تابع زمانی الگوریتم های بازگشتی و غیر بازگشتی را پیدا کنم؟

    function fib(n)
    i=1; j=0; k=0; h=1;
    while n>0 do
    if n is odd then
    t=jh;
    j=ih+jk+t;
    i=ik+t;
    t=h^2;
    h=2kh+t;
    k=k^2+t
    n=n div 2;
    return j

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •