• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność obliczeniowa algorytmów

VPS Starter Arubacloud
0 głosów
367 wizyt
pytanie zadane 5 grudnia 2019 w Algorytmy przez progNewbie Obywatel (1,130 p.)

Cześć,

Potrzebuję zapisać złożoność obliczeniową trzech różnych algorytmów:

function znajdzNajw($tab, $comment){
    $max1 = $tab[0];
    $max2 = $tab[1];
    
    for($i = 2; $i < count($tab); $i++){
        $max1 >= $max2 ? ($tab[$i] > $max2 ? $max2 = $tab[$i] : $max2 = $max2) : ($tab[$i] > $max1 ? $max1 = $tab[$i] : $max1 = $max1);
    }
    
    $najw = array($max1, $max2);
    return wyswietlPare($najw, $comment);
}

function znajdzNajm($tab, $comment){
    $min1 = $tab[0];
    $min2 = $tab[1];
    
    for($i = 2; $i < count($tab); $i++){
        $min1 > $min2 ? ($min1 > $tab[$i] ? $min1 = $tab[$i] : $min1 = $min1) : ($min2 > $tab[$i] ? $min2 = $tab[$i] : $min2 = $min2);
    }
    
    $najm = array($min1, $min2);
    return wyswietlPare($najm, $comment); 
}

function sortujTab($tab){
    
    for($i = 0; $i < count($tab); $i++){
        for($j = 0; $j < count($tab) - 1; $j++){
            if($tab[$j] > $tab[$j + 1]){
                $tmp = $tab[$j + 1];
                $tab[$j + 1] = $tab[$j];
                $tab[$j] = $tmp;
            }
        }
    }
    
    return $tab;
}

Czy złożonością obliczeniową dla funkcji:

znajdzNajw i znajdzNajm to O(N)

sortujTab to O(N^2)

2 odpowiedzi

0 głosów
odpowiedź 6 grudnia 2019 przez mmarszik Mądrala (7,390 p.)
Trudno powiedzieć, do czego to potrzebujesz? Jak do praktycznego zadania, to najlepiej zmierzyć czasy. Jak do teoretycznego, to najlepiej algorytm zaprezentować w metakodzie, mój ulubiony meta-kod jest taki jak w książce Cormena.

Pozdrrawiam
komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)
W zasadzie to nie bardzo wiem do czego to potrzebuje.

Mam w pracy domowej, że oprócz schematu blokowego, punktowego trzeba jeszcze zapisać złożoność obliczeniową dla tych funkcji.
komentarz 6 grudnia 2019 przez mmarszik Mądrala (7,390 p.)
Zależy od implementacji w danej wersji danego języka programowania i biblioteki. Chyba że czas jednej instrukcji przyjmiesz równy jeden, nie ważne czy count liczy ilość elementów czy ma gdzieś zapamiętaną tę ilość. Różnice też mogą wynikać z tablic, mogą być tablicami skojarzeniowymi zrealizowanymi jako drzewa, jako hash-table, albo jako liniowe tablice.

Ja w praktyce mierzę czasy, a teoretycznie można rozważać na jakimś dobrze zdefiniowanym modelu obliczeń, jak to np. jest w książce Cormena.
0 głosów
odpowiedź 6 grudnia 2019 przez MateuszRus Obywatel (1,060 p.)

Cześć, zerknij tu. Pisałem trochę na temat złożoności i może Ci to jakoś pomoże! :) 

 

LINK

komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)
Hej,

Widziałem, czytałem - jako tako rozumiem o czym tam jest napisane.

Jednakże od praktycznej strony mam tyle pytań, że nie wiem od czego zacząć. eh
komentarz 6 grudnia 2019 przez MateuszRus Obywatel (1,060 p.)
Pytaj tu albo prywatnie :)
komentarz 6 grudnia 2019 przez progNewbie Obywatel (1,130 p.)
Na początku to chciałbym wiedzieć czy jeśli mamy pętle for + 2 operacje przypisania poza pętlą for to jest to:

O(N) czy O(N+2) ?
komentarz 6 grudnia 2019 przez MateuszRus Obywatel (1,060 p.)
N+2.

N to ilość iteracji pętli, natomiast każde przypisanie to dodanie 1. N + 1 + 1 daje N + 2.

Jeżeli następuje na koniec metody jeszcze RETURN, to wtedy on też jest osobną operacją i złożoność będzie wynosić N + 3.

 

Operacje przypisania nie wpływają aż tak na złożoność algorytmu jak samo N, czyli ilość elementów tablicy, po których iterujemy. Niezależnie, czy w operacji przypisania dasz na przykład wartość liczbową równą 10 czy 10000 to nie wpłynie to na wydajność. Inaczej będzie z wielkością tablicy po której iterujesz. :) jeżeli będzie ona 10 elementowa to pętla wykona się dużo szybciej niż przy tablicy z 10000 elementami.

Podobne pytania

0 głosów
1 odpowiedź 521 wizyt
pytanie zadane 1 listopada 2020 w Algorytmy przez niezalogowany
0 głosów
1 odpowiedź 321 wizyt
pytanie zadane 14 czerwca 2021 w Algorytmy przez Tanormalnie Użytkownik (550 p.)
0 głosów
1 odpowiedź 209 wizyt
pytanie zadane 25 kwietnia 2020 w C i C++ przez Tacoo Nowicjusz (150 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...