Cześć wszystkim! Mam do wykonania projekt na studia, którego polecenie brzmi tak:
"Zweryfikować ocenę średniej i pesymistycznej złożoności wyszukiwania liniowego i binarnego."
Mam już zrobioną część z pesymistyczną złożonością, ale dalej nie mam i nie potrafię ogarnąć tej średniej. Po długich walkach odpuściłem dalsze dochodzenie do celu samemu i przychodzę tutaj prosić o pomoc. Kod mojego programu jest poniżej, byłbym baaardzo wdzięczny jeśli ktoś pomógłby mi to zrozumieć i dopiąć do końca!
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace Projekt1
{
class Program
{
const int NIter = 10;
static int[] TestVector;
static ulong OpComparisonEQ;
static bool IsPresent_LinearTim(int[] Vector, int Number)
{
for (int i = 0; i < Vector.Length; i++)
if (Vector[i] == Number)
return true;
return false;
}
static bool IsPresent_LinearInstr(int[] Vector, int Number)
{
for (int i = 0; i < Vector.Length; i++)
{
OpComparisonEQ++;
if (Vector[i] == Number) return true;
}
return false;
}
static bool IsPresent_BinaryTim(int[] Vector, int Number)
{
int Left = 0, Right = Vector.Length - 1, Middle;
while (Left <= Right)
{
Middle = (Left + Right) / 2;
if (Vector[Middle] == Number) return true;
else if (Vector[Middle] > Number) Right = Middle - 1;
else Left = Middle + 1;
}
return false;
}
static bool IsPresent_BinaryInstr(int[] Vector, int Number)
{
int Left = 0, Right = Vector.Length - 1, Middle;
while (Left <= Right)
{
Middle = (Left + Right) / 2;
OpComparisonEQ++;
if (Vector[Middle] == Number) return true;
else
{
OpComparisonEQ++;
if (Vector[Middle] == Number) Right = Middle - 1;
else Left = Middle + 1;
}
}
return false;
}
static void LinearMaxInstr()
{
OpComparisonEQ = 0;
bool Present = IsPresent_LinearInstr(TestVector, TestVector.Length - 1);
Console.Write("\t" + OpComparisonEQ);
}
static void LinearMaxTim()
{
double ElapsedSeconds;
long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
for (int n = 0; n < (NIter + 1 + 1); ++n)
{
long StartingTime = Stopwatch.GetTimestamp();
bool Present = IsPresent_LinearTim(TestVector, TestVector.Length - 1);
long EndingTime = Stopwatch.GetTimestamp();
IterationElapsedTime = EndingTime - StartingTime;
ElapsedTime += IterationElapsedTime;
if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
}
ElapsedTime -= (MinTime + MaxTime);
ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
Console.Write("\t" + ElapsedSeconds.ToString("F2") + "s");
}
static void BinaryMaxInstr()
{
OpComparisonEQ = 0;
bool Present = IsPresent_BinaryInstr(TestVector, TestVector.Length - 1);
Console.Write("\t" + OpComparisonEQ);
}
static void BinaryMaxTim()
{
double ElapsedSeconds;
long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
for (int n = 0; n < (NIter + 1 + 1); ++n)
{
long StartingTime = Stopwatch.GetTimestamp();
bool Present = IsPresent_LinearTim(TestVector, TestVector.Length - 1);
long EndingTime = Stopwatch.GetTimestamp();
IterationElapsedTime = EndingTime - StartingTime;
ElapsedTime += IterationElapsedTime;
if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
}
ElapsedTime -= (MinTime + MaxTime);
ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
Console.WriteLine("\t" + ElapsedSeconds.ToString("F2") + "s");
}
static void Main(string[] args)
{
Console.WriteLine("Size \tLMaxI \tLMaxT \tBMaxI \tBMaxT");
for (int ArraySize = 26843545; ArraySize <= 268435450; ArraySize += 26843545)
{
Console.Write(ArraySize);
TestVector = new int[ArraySize];
for (int i = 0; i < TestVector.Length; ++i)
{ TestVector[i] = i; }
LinearMaxInstr();
LinearMaxTim();
BinaryMaxInstr();
BinaryMaxTim();
}
Console.ReadKey();
}
}
}