Program do obliczania złożoności obliczeniowej
Program bada średnią ilość iteracji oraz średni czas wykonania algorytmu, analizuje odchylenie standardowe oraz błąd względny.
Odchylenie standardowe mówi jak bardzo dane są rozproszone wokół średniej.
Małe odchylenie - dane są zbliżone do średniej, małe rozproszenie.
Duże odchylenie standardowe - dane są bardziej rozproszone, duże zróżnicowanie.
Błąd względny mówi jak bardzo pomiar odbiega od wartości prawdziwej(lub wzorcowej) - w procentach.
Im mniejszy, tym dokładniejszy pomiar.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Globalization;
namespace Computationalcomplexity
{
public class CounterAnalyzer
{
private static long iterationCount; //przechowujemy liczbe iteracji w long
public static void ResetCounter() //metoda do resetowania liczby iteracji; liczymy pomiar osobno nie liczymy SUMY
{
iterationCount = 0;
}
//funkcja do liczenia średniej liczby iteracji
/*Chcemy, żeby ta funkcja:
przyjmowała algorytm, który będziemy testować,
kilka razy go uruchamiała,
zapisywała, ile było iteracji w każdej próbie,
na końcu policzyła średnią; */
//Func<int, int> algorithm - f. która liczymy; n - rozmiar danych; iterations - ile razy powtarzamy pomiar
public static double ComputeMeanIterations(Func<int, int> algorithm, int n, int iterations)
{
long[] iterationResults = new long[iterations]; //tablica na wyniki z każdej próby
for (int i = 0; i < iterations; i++)
{
iterationCount = 0; //reset licznika przed każdym uruchomieniem
algorithm(n); //startujemy algorytm
iterationResults[i] = iterationCount; //zapisujemy ile było iteracji
}
//obliczamy średnią ze wszystkich prób
double average = iterationResults.Average();
return average;
}
//funkcja do obliczania odchylenia standardowego l. iteracji
/*
* Zbieramy wszystkie liczby iteracji (tak samo jak w poprzedniej funkcji).
* Liczymy ich średnią.
* Potem dla każdej z nich sprawdzamy, jak bardzo odbiega od średniej.
* Sumujemy te różnice, dzielimy przez liczbę prób,
* i na koniec bierzemy pierwiastek kwadratowy.
*/
public static double ComputeDeviationIterations(Func<int, int> algorithm, int n, int iterations)
{
long[] iterationResults = new long[iterations]; //tu trzymamy wyniki
for (int i = 0; i < iterations; i++)
{
iterationCount = 0; //resetujemy licznik
algorithm(n); //startujemy algorytm
iterationResults[i] = iterationCount; //zapisujemy wynik
}
//liczymy odchylenie standardowe
double average = iterationResults.Average(); //średnia
double sumOfSquares = 0;
for (int i = 0; i < iterations; i++)
{
double difference = iterationResults[i] - average; //różnica od średniej
sumOfSquares = sumOfSquares + (difference * difference); //podnosimy do kwadratu i dodajemy
}
double standardDevitation = Math.Sqrt(sumOfSquares / iterations); //pierwiastek kwadratowy; odchylenie populacyjne
return standardDevitation;
}
/*
* average → to średnia liczba iteracji (z funkcji, którą już napisaliśmy),
* dzielimy standardDeviation / average → otrzymujemy proporcję rozrzutu,
* mnożymy ×100 → żeby mieć procent.
*
* Odchylenie standardowe mówi, jak bardzo wyniki „skaczą” wokół średniej.
* Małe odchylenie = pomiary są do siebie podobne.
* Duże odchylenie = pomiary są bardzo różne.
*/
public static double ComputeErrorIterations(double average, double standardDevitation)
{
if (average == 0) //nie dzielic przez 0
return 0;
double relativeError = (standardDevitation / average) * 100;
return relativeError;
}
public static int QuadraticWithIterations(int n)
{
iterationCount = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int x = i * j; // jakaś praca
iterationCount++; // zliczamy operację
}
}
return 0;
}
}
public class TimeAnalyzer
{
/*
* mierzy czas wykonania algorytmu iterations razy,
zapisuje każdy wynik do tablicy,
liczy średnią,
i ją zwraca w milisekundach.
*/
public static double ComputeMeanTime(Action algorithm, int iterations) //iterations ile razy powtarzamy pomiar
{
double[] timeResults = new double[iterations]; // tablica na wyniki pomiarów
for (int i = 0; i < iterations; i++)
{
Stopwatch stopwatch = Stopwatch.StartNew();// start pomiaru czasu
algorithm(); //startujemy algorytm
stopwatch.Stop(); // zatrzymujemy stoper
timeResults[i] = stopwatch.Elapsed.TotalMilliseconds; // zapisujemy czas (w ms)
}
double average = timeResults.Average(); // liczymy średnią
return average;
}
public static double ComputeDeviationTime(Action algorithm, int iterations)
{
double[] timeResults = new double[iterations];
for (int i = 0; i < iterations; i++)
{
Stopwatch stopwatch = Stopwatch.StartNew();
algorithm();
stopwatch.Stop();
timeResults[i] = stopwatch.Elapsed.TotalMilliseconds;
}
double average = timeResults.Average();
double sumOfSquares = 0;
for (int i = 0; i < iterations; i++)
{
double difference = timeResults[i] - average; // różnica od średniej
sumOfSquares = sumOfSquares + (difference * difference); // dodajemy kwadrat różnicy
}
double standardDeviation = Math.Sqrt(sumOfSquares / iterations);
return standardDeviation;
}
public static double ComputeErrorTime(double averageMs, double standardDeviationMs)
{
if (averageMs == 0.0) return 0.0; // zabezpieczenie
return (standardDeviationMs / averageMs) * 100.0;
}
public static void QuadraticWork(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int x = i * j; // prosta praca obliczeniowa
}
}
}
}
internal class Program
{
static void Main(string[] args)
{
int size = 2000; // rozmiar danych
int trials = 5; // ile powtórzeń dla pomiaru
Console.WriteLine("===== ZESTAW 1: ŚREDNIA LICZBA ITERACJI =====");
double meanIter = CounterAnalyzer.ComputeMeanIterations(CounterAnalyzer.QuadraticWithIterations, size, trials);
double devIter = CounterAnalyzer.ComputeDeviationIterations(CounterAnalyzer.QuadraticWithIterations, size, trials);
double errIter = CounterAnalyzer.ComputeErrorIterations(meanIter, devIter);
Console.WriteLine($"O(n²): średnia={meanIter:0} odchylenie={devIter:0.##} błąd={errIter:0.00}%");
Console.WriteLine("\n===== ZESTAW 2: ŚREDNI CZAS WYKONANIA =====");
double meanTime = TimeAnalyzer.ComputeMeanTime(() => TimeAnalyzer.QuadraticWork(size), trials);
double devTime = TimeAnalyzer.ComputeDeviationTime(() => TimeAnalyzer.QuadraticWork(size), trials);
double errTime = TimeAnalyzer.ComputeErrorTime(meanTime, devTime);
Console.WriteLine($"O(n²): średni={meanTime:0.##} ms, odchylenie={devTime:0.##} ms, błąd={errTime:0.00}%");
//ZAPISYWANIE DO CSV
/*string filePath = "results.csv";
using (StreamWriter writer = new StreamWriter(filePath, false, Encoding.UTF8))
{
writer.WriteLine("RozmiarDanych || SredniaIteracji || OdchylenieIteracji || BladIteracji || SredniCzas_ms || Odchylenie_ms || BladCzasu_%");
int[] sizes = { 100, 500, 1000, 2000}; // różne rozmiary danych
foreach (int size in sizes)
{
double meanIter = CounterAnalyzer.ComputeMeanIterations(CounterAnalyzer.QuadraticWithIterations, size, trials);
double devIter = CounterAnalyzer.ComputeDeviationIterations(CounterAnalyzer.QuadraticWithIterations, size, trials);
double errIter = CounterAnalyzer.ComputeErrorIterations(meanIter, devIter);
double meanTime = TimeAnalyzer.ComputeMeanTime(() => TimeAnalyzer.QuadraticWork(size), trials);
double devTime = TimeAnalyzer.ComputeDeviationTime(() => TimeAnalyzer.QuadraticWork(size), trials);
double errTime = TimeAnalyzer.ComputeErrorTime(meanTime, devTime);
writer.WriteLine($"{size} || {meanIter:0.##} || {devIter:0.##} || {errIter:0.##}% || {meanTime:0.##}ms || {devTime:0.##}ms || {errTime:0.##}%");
}
}
Console.WriteLine("\nWyniki zapisano do pliku results.csv");
*/
}
}
}