Czy mogę w ten sposób poprawnie porównywać algorytmy?

Witam, chciałem sprawdzić różnicę pomiędzy rekurencją, a pętlą wyrażoną w milisec. przy obliczaniu n-tego wyrazu ciągu fibonacciego.
Lecz nie jestem pewien, czy jest to sposób który można wykorzystać "gdzieś dalej" (tzn. uczelnia/praca)

Algorytmy:

Rekurencja

static int rekur(int a)
        {
            if (a == 1 || a == 2)
                return 1;
         
            return rekur(a - 1) + rekur(a - 2);
        }

Pętla

    static ulong petla(int a)
        {
            if (a == 1 || a == 2)
            {
                return 1;
            }
            else
            {
                ulong stack = 1;
                ulong oldvar = 1;
                for (int i = 3; i <= a; i++)
                {
                    ulong temp = stack;
                    stack = stack + oldvar;
                    oldvar = temp;
                }

                return stack;
            }
        }

(Użyłem inta i ulonga, ponieważ zauważyłem, że dla pętli mogę obliczać o wiele większe liczby)

rekur(40) = 102334155
petla(40) = 102334155

Wyniki się zgadzają, więc liczy dobrze.

Następnie wrzuciłem oba algorytmy w osobne pętle które wyliczały

rekur(1) rekur(2) rekur(3)...rekur(40)
petla(1) petla(2) petla(3)...petla(40)

Mierzyły one czas każdego z nich, który następnie dodałem do tablicy (tab[x] += wartość), a żeby dostać w miarę przyzwoite przybliżenie powtórzyłem obie pętle po 40razy, a później podzieliłem każdy tab[x] przez 40.

           double[] rekur_tab = new double[41]; ///długość 41, bo zegar zaczyna od 1, 
           a chciałem sprawdzić dla 40liczb.
           double[] petla_tab = new double[41];
           int ilosc = 40;
         
            

            Stopwatch timer = new Stopwatch();
            for (int i = 1; i <= 40; i++)
            {
                for (int a = 1; a <= ilosc; a++)
                {
                    timer.Restart();
                    timer.Start();
                    rekur(a);
                    timer.Stop();
                    rekur_tab[a] += Convert.ToDouble(timer.ElapsedMilliseconds);
                    
                }
            }   
   
            Console.WriteLine("____");

            for (int i = 1; i <= 40; i++)
            {
                for (int a = 1; a <= ilosc; a++)
                {

                    timer.Restart();
                    timer.Start();
                    petla(a);
                    timer.Stop();
                    petla_tab[a] += Convert.ToDouble(timer.ElapsedMilliseconds);

                    ///  Console.WriteLine(timer.Elapsed + " | " + timer.ElapsedMilliseconds + "ms");
                }
            }


         for (int a = 0; a < petla_tab.Count(); a++)
               {
                   Console.WriteLine(petla_tab[a] / ilosc);
               }
            Console.WriteLine(  "_____");

            for (int a = 0; a < rekur_tab.Count(); a++)
            {
                Console.WriteLine(rekur_tab[a] / ilosc);
            }
  Console.ReadKey();

Wynik dla rekurencji:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0,025
0
0,15
0,45
1,3
2,9
4,55
8,3
12,55
21,65
34,2
52
86,475
143,8
231,375
377,675
603,575
991,45
1590,3
2536,225
4133,95

Wynik dla pętli
BTW: petla(880000) = 7ms.

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Moja propozycja to rekurencja + memoization, złożoność obliczeniowa O(n)
http://rextester.com/NEQO10809

//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        static ulong[] m = Enumerable.Repeat<ulong>(0, 9999).ToArray();
        
        static ulong rekur(int a)
        {   
            if (a == 1 || a == 2)
                return 1;
            if(m[a] != 0) return m[a]; 
            
            //return rekur(a - 1) + rekur(a - 2);
            return m[a] = rekur(a - 1) + rekur(a - 2);
        }
        
        public static void Main(string[] args)
        {
            ulong z = 0;
            int upperBound = 40;
            z = rekur(upperBound);
            Console.WriteLine(z);
            foreach(var x in Enumerable.Range(1, upperBound)) Console.WriteLine(String.Format("{0} {1}", x, m[x]));
        }
    }
}

@reptile333 @WeiXiao algorytm rekurencyjny (skoro już go piszemy), to najlepiej napisać tak by umożliwić TCO (chociaż nie wiem czy .NET to wspiera, ale chyba tak, skoro mają F#):

static ulong RecurTco(int n_1, int n_2, int i)
{
    if (i == 0)
        return n_1;

    return RecurTco(n_1 + n_2, n_ 1, i - 1);
}

Pisane o 0300 z pamięci, bez testowania. Może być błąd, do znalezienia w formie ćwiczenia.

1. zwykle, w nowszych rozwiązaniach, ciąg Fibonacciego zaczyna się od 0
2. wersję iteracyjną można zapisać bez zmiennej tymczasowej
3. przy 40 ten program więcej czasu spędza na zarządzaniu timerem niż na algorytmie, przy czym nie mierzysz ile czasu zajmuje to zarządzanie (przydaje się zrobić pusty przebieg)
4. nie rozgrzewasz maszyny wirtualnej, jeśli C# jest podobny w tym względzie do Javy którą znam - powinieneś.

Poradnik:

• (C# i Java): https://www.itu.dk/people/sestoft/papers/benchmarking.pdf

vpiotr napisał(a):

3. przy 40 ten program więcej czasu spędza na zarządzaniu timerem niż na algorytmie, przy czym nie mierzysz ile czasu zajmuje to zarządzanie (przydaje się zrobić pusty przebieg)

tzn?