Algorytm już napisałem, schemat blokowy i instrukcje krok po kroku też. Problem został jedynie ze złożonością obliczeniową. Podam poniżej kod w PHP, prosiłbym o jakiekolwiek wskazówki.
Rozumiem, że złożoność w dużej mierze zależy od ilości danych. Załóżmy więc że liczb w tablicy jest 20. Dziękuje z góry za pomoc.
Co wiem:
W pierwszej pętli sprawdzam każdy element czyli tyle ile liczb tyle sprawdzeń. (złożoność liniowa?)
W drugiej pętli zaś sprawdzam każdy element który jest maximum (z pierwszej pętli) i tutaj mam ..? No właśnie co?..
Plus jak to zapisać (obliczenia) ?
Kod: Zaznacz cały
<?php
function znajdzLiczby($liczby) {
$max = $liczby[0];
$ml = 0;
$ile = 0;
foreach ($liczby as $k => $v) {
if ($k != 0) {
if ($v > $max) {
$max = $v;
unset($poz);
$poz[] = $k;
$ile = 1;
} else if ($v == $max) {
$poz[] = $k;
$ile++;
}
}
}
if ($ile == 1) {
$ml = 0;
} else {
for ($j = 0; $j <= $ile - 2; $j++) {
if ($j == 0) {
$ml = $poz[$j + 1] - $poz[$j];
} else
if ($poz[$j + 1] - $poz[$j] < $ml) {
$ml = $poz[$j + 1] - $poz[$j];
}
}
}
$result['max'] = $max;
$result['ile'] = $ile;
$result['ml'] = $ml;
return $result;
}
?>Trochę moich wypocin... czy ktoś mógłby rzucić okiem?
wg.
Ale nie widzę nic z tego wzoru...
t1 - wczytywanie danych
t2 – przypisywanie wartości
t3a – sprawdzenie
t3b – skok
t4 – unset
t5 - wypisywanie
Złożoność czasowa optymistyczna
1*t1 + 5*t2 + (n+1)*t3a + 1*t3b + (n+1)*2*t3a + (n+1)*3*t2 + (n+1)*t4 + 1*t3a + 1*t2 + 3*t5 =
t1 + 9*(n+1)*t2 + (2n+5)*t3a + 1*t3b + (n+1)*t4 + 3*t5
ta = t3a + t3b
tb = t2 + t4
tc = t1 + t5
T(n) = ta*(2n+5)
T(n) = tb*(10n+10)
T(n) = tc*4
T(n) = ta*(2n+5) * tb*(10n+10) * tc*4
POMOCY:P