Witam!
Mam do zrobienia projekt, w którym mam do zbadania dwa algorytmy przeszukujące liniowe(O(n)) i binarny O(log(n)). W zadaniu muszę zrobić tablicę sortującą rosnąco oraz zrobić do tych algorytmów punkty pomiarowe, których ma być minimum 30. Najmniejsza tablica ma mieć 2000k a największa 2^28 elementów typu int. Muszę zrealizować przypadki pesymistyczne i przypadki średnie dla wyszukiwania liniowego i wyszukiwania binarnego a dodatkowo zrobić też wersję z instrumentacją.
Zrobiłem wyszukiwanie binarne, wyszukiwanie liniowe oraz przypadek pesymistyczny dla obydwóch tych algorytmów, ale nie rozumiem jak mam zrobić wersję z instrumentacją i jak mogę wykonać przypadek średni. Byłbym wdzięczny za ewentualne wytłumaczenie lub nakierowanie mnie co mogę zrobić. Niżej załączam linijki kodu, które dotychczas napisałem.
// Posortowanie tablicy rosnąco
public static int[] Posortowane(int rozmiar)
{
int[] tab = new int[rozmiar];
for(int i = 0; i < tab.Length; i++)
{
tab[i] = i;
}
return tab;
}
// wyszukiwanie binarne
public static int WyszukiwanieBinarne(int[] tab, int szukanie)
{
int left = 0;
int right = tab.Length - 1;
while(left <= right)
{
int CurrentPosition = left + (right - left) / 2;
if (tab[CurrentPosition] == szukanie)
return CurrentPosition;
if (tab[CurrentPosition] < szukanie)
left = CurrentPosition + 1;
if (tab[CurrentPosition] > szukanie)
right = CurrentPosition - 1;
}
return -1;
}
// wyszukiwanie liniowe
public static int WyszukiwanieLiniowe(int[] tab, int element)
{
for(int i = 0; i < tab.Length; i++)
{
if (tab[i] == element)
return i;
}
return -1;
}
// wyszukiwanie binarne pesymistyczne
int rTablicy = Convert.ToInt32(Math.Pow(2, 28)); // rozmiar tablicy
int[] tablica = Pomocna.Posortowane(rTablicy); // tablica posortowana
Stopwatch stoperek = new Stopwatch();
double wynik = 0;
for(int i = 0; i < rTablicy; i+=8000000)
{
stoperek.Reset();
stoperek.Start();
tablica = Pomocna.Posortowane(i);
WyszukiwanieBinarne(tablica, -1);
stoperek.Stop();
wynik = stoperek.ElapsedTicks;
Console.WriteLine($"{wynik};{i}");
}
// wyszukiwanie liniowe pesymistyczne
int rTablicy = Convert.ToInt32(Math.Pow(2, 28)); // rozmiar tablicy
int[] tablica = Pomocna.Posortowane(rTablicy); // tablica posortowana
for(int i = 0; i < rTablicy; i+=8000000 ) // wyszukiwanie liniowe pesymistyczne
{
tablica = Pomocna.Posortowane(i);
stoperek.Reset();
stoperek.Start();
WyszukiwanieLiniowe(tablica, -1);
stoperek.Stop();
wynik = stoperek.ElapsedMilliseconds;
Console.WriteLine($"{wynik};{i}");
}