Cześć,
Stworzyłem wykres złożoności czasowej na podstawie danych(ilość elementów tablicy i czas wykonania), niestety nie pokrywa on się ze z faktyczną złożonością programu jaką jest O(logn). Wykres bardziej przypomina funkcję liniową niż logarytmiczną. Czas wykonania programu dla danego "n" wypisywałem mniej-więcej, ponieważ przy kilku próbach wykonania programu dla danej wielkości tablicy różnice czasowe wynosiły 20-80ms a przy większym 'n' różnice były większe. Czy mógłby ktoś to przeanalizować i powiedzieć gdzie popełniłem błąd, że wykres nie pokrywa się z faktyczną złożonością programu? ```
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Projekt</title>
</head>
<body>
<script>
//generator tablicy
var size = 10000000; // ilość elementów tablicy
var max = 10000; // maksymalna możliwa liczba do wylosowania
var tab = [];
for(k=0; k<size; k++)
{
los = Math.floor(Math.random() * max) + 1;
tab[k] = los;
}
tab.sort(function(a, b) {return a - b;}); // uporządkowanie tablicy
//------------------------------------------------
function licz(tab, w, n)
{
//indeks pierwszego wystąpienia "w"
idMin = pierwszy(tab, 0, n-1, w, n);
//jeśli "w" nie istnieje w tablicy
if (idMin == -1){return idMin};
//indeks ostatniego wystąpienia
idMax = ostatni(tab, idMin, n-1, w, n);
ilosc = idMax-idMin+1;
//zwracamy ilość powtórzeń wartości "w"
return ilosc;
}
function pierwszy(tab, l, p, w, n) //indeks pierwszego wystąpienia
{
if(l <= p) //l - początek zakresu listy p - koniec zakresu listy
{
mid = Math.floor((l+p)/2);
if((mid == 0 || w > tab[mid-1])&&(tab[mid] == w))
{
return mid; // zwraca indeks pierwszego wystapienia
}
else if(w > tab[mid])
{
return pierwszy(tab, (mid+1), p, w, n);
}
else
{
return pierwszy(tab, l, (mid-1), w, n);
}
}
return -1;
}
function ostatni(tab, l, p, w, n)//indeks ostatniego wystąpienia
{
if(l <= p)
{
mid2 = Math.floor((l+p)/2);
if((mid2 == n-1 || w < tab[mid2+1]) && (tab[mid2] == w))
{
return mid2; //zwraca indeks ostatniego wystąpienia
}
else if(w < tab[mid2])
{
return ostatni(tab, l, (mid2-1), w, n);
}
else
{
return ostatni(tab, (mid2+1), p, w, n);
}
}
}
//Wywołanie funkcji
w = 49; // szukana wartość
n = tab.length; // długość tablicy
console.time("test");
ile = licz(tab, w, n); // zwraca liczba powtórzeń szukanej wartośći w tablicy
console.timeEnd("test");
if(ile == -1)
{
document.write("Wartość "+w+" pojawiła się 0 razy<br/>");
}
else
{
document.write("Wartość "+w+" pojawiła się "+ile+" raz/razy<br/>");
}
//console.table(tab); // wypisanie tablicy
</script>
</body>
</html>
[wykres.xlsx](https://4programmers.net/assets/34819/nXDNsLuzHKvRp1UritJjVdRNoluTuJgCq8sSvr4C.xlsx)