(PHP) Algorytm Max elementy w zbiorze, ich minimalna roznica

Dla specjalistów Programowanie
#1

Witam, mam do utworzenia i analizy algorytm wyznaczenia liczby wystąpień maksymalnego elementu w tablicy oraz minimalnej odległości między elementami o maksymalnej wartości.

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.

<?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;

}


?>
#2

Złożoność owszem zależy od ilości danych ale nie w taki sposób jak ty to interpretujesz, ponieważ dla każdej wartości 20, 21, 22, … musiałbyś na nowo liczyć złożoność.

  1. Tablica n elementowa

W pierwszej pętli sprawdzasz każdy element czyli masz złożoność O(n)

W drugiej pętli zaś sprawdzasz każdy element który jest maximum i tutaj masz O(k) gdzie k liczba elementów max.

Więc złożoność jest O(n+k) - jest to przypadek kiedy złożoność algorytmu jest wrażliwa na jego wynik.

Tutaj wykazałem złożoność czasową (najczęściej rozpatrywaną), można jeszcze policzyć złożoność pamięciową.

#3

Rozumiem, że złożoność pamięciowa dotyczy “ilości pamięci” wykorzystywanej przez każdą operacje? (dodawanie,porównywanie itp)

W takim razie, jak sprawdzić - albo czy jest jakieś założenie ile pamięci potrzebuje konkretna operacja?

#4

Uważam, że tutaj znajdziesz info dotyczące złożoności obliczeniowej.

http://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa

#5

Oczywiście, ten link już przeglądałem:)

Tyle, że ja mam udokumentować złożoność jakimiś obliczeniami i teraz jak to zapisac?

#6

powołując się na punkt 2.16. regulaminu

Tutaj nie odrabiamy prac domowych

#7

To nie tyle ze praca domowa, co nie wiedziałem jak to ma wyglądać.

http://edu.i-lo.tarnow.pl/inf/utils/010_2010/0216.php dla potomnych.

Dziękuje za pomoc.

– Dodane 13.01.2012 (Pt) 23:08 –

Trochę moich wypocin… czy ktoś mógłby rzucić okiem?

wg. poradnika z poprzedniego postu…

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