C# Klasa StopWatch() - Czas działania metody

Witam,

Mam problem z wynikami jakie prezentuje użyta klasa StopWatch.

Na zadanie z algorytmiki musiałem ułożyć algorytm, który dla dowolnej tablicy m x n (z elementami całkowitymi) zwraca indeks wiersza o największej nieparzystej sumie elementów.
Algorytm działa prawidłowo (metoda poniżej), jednakże dodatkowo miałem zbadać złożoność tego algorytmu dołączając pomiar czasu dla coraz większej tablicy.

 
public static List<int> MaxOddRow(int[,] TargetArray)
        {
            List<int> ResultList = new List<int>() {-1};
            int maxSum = -1;
            int tempSum = 0;
            for (int i = 0; i < TargetArray.GetLength(0); i++)
            {
                tempSum = 0;
                for (int j = 0; j < TargetArray.GetLength(1); j++)
                {
                    tempSum += TargetArray[i, j];
                }
                if (tempSum % 2 != 0)
                {
                    if (tempSum > maxSum)
                    {
                        maxSum = tempSum;
                        ResultList = new List<int>() { i };
                    }
                    else if (tempSum == maxSum)
                    {
                        ResultList.Add(i); 
                    }
                }
            }

            return ResultList;
        }

Wyniki są co najmniej dziwne... algorytm dla 225 elementów działa prawie dwukrotnie dłużej niż dla 441 elementów.
Wyniki pomiaru poniżej.

Wymiar Tablicy | Czas w taktach procesora
3 X 3 | 1452
9 X 9 | 1659
15 X 15 | 1843
21 X 21 | 1029
27 X 27 | 1058
33 X 33 | 1061
39 X 39 | 1086
45 X 45 | 1136
51 X 51 | 1095
57 X 57 | 1147
63 X 63 | 1137

Dodatkowo poniżej sam fragment metody Main zawierający instancje klasy StopWatch.

static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            int[,] TargetArray = InitialArray();
            List<int> ResultList = new List<int>();
            PrintTable(TargetArray);
            sw.Start();
            ResultList = MaxOddRow(TargetArray);
            sw.Stop();
            ResultInterpreter(ResultList);
            Console.WriteLine("\n Czas wykonania algorytmu: {0}", sw.ElapsedTicks);
            Console.ReadKey();
        }
 

Może ktoś ma jakiś pomysł dlaczego tak się dzieje? Prośba o pomoc.

To za mała próbka. Uruchom funkcję np. milion razy, tak by całość trwała przynajmniej kilka sekund.

Rzeczywiście, masz rację. Dzięki;) Przy tak małej próbie na wynik pomiaru mogły wpływać zachowanie kompilatora CLR w tym C# Garbage Collector, inicjalizacje list, obiektów etc.

Natomiast, po zwiększeniu próby wyniki zaskoczyły mnie jeszcze bardziej... Iteracja ograniczona zagnieżdżona w drugiej iteracji ograniczonej musi dać złożoność przynajmniej O(N ^ 2).
Dobrałem przyrost rozmiaru elementów w tablicy liniowy (w poniższej tabeli) a czas również rośnie liniowo, a nie kwadratowo...

Wymiar Tablicy m x m | Liczba elementów | Czas w ms
1500 | 2250000 | 23
1600 | 2560000 | 26
1694 | 2870000 | 29
1783 | 3180000 | 32
1868 | 7520000 | 76

Wydaje mi się, że dalej popełniam jakiś błąd... tylko teraz już zupełnie nie wiem gdzie.

Dodam wpis zamykający post.

Wyniki są jak najbardziej prawidłowe gdyż złożoność obliczeniowa tego algorytmu jest rzeczywiście O (n^2) pod warunkiem, że sprawdzając zależność zmiennych przy tablicy kwadratowej odwołuje się do n (czyli wierszy lub kolumn tabeli a nie do n x n czyli liczby elementów tablicy).
Dla tablicy nie kwadratowej złożoność będzie O (m*n).

Wartości poznawcze z tego postu są dwie:

1. Stosujcie możliwe duża liczbę danych, aby uniknąć zaburzenia wyników wynikające z jak najbardziej poprawnego działania frameworku .NET i kompilatora
2. Jeżeli stosujecie wartości losowe tak jak ja w tym przypadku, zwiększacie próbę wyniku przez dodanie dodatkowej pętli na metodzie. Czas działanie się zwielokrotni, ale wyniki staną się uśrednione.

Przykład poniżej:

            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < 100; ++i)
                 { MaxOddRow(TargetArray); 
            sw.Stop();
            Console.WriteLine("\n Czas wykonania algorytmu: {0}", sw.ElapsedTicks);
 

Ps. Oczywiście pętle if mają złożoność niższego rzędu i tak nie wpłyną na złożoność n^2 całego algorytmu, ale i tak dane będą bliższe rzeczywistośco

Pamiętaj też o tym, że CLR kompiluje metodę przy pierwszym wywołaniu. Dlatego należy najpierw raz wywołać metodę, a dopiero potem rozpocząć mierzenie z właściwymi danymi, tak aby niepotrzebnie nie zwiększać czasu działania algorytmu o czas kompilacji metody.