[FortresMaximus]

Cześć mirki, moglby mi ktoś pomoc odpowiedzieć na te pytania? Udzielilem odpowiedzi a na koniec pokazalo mi 0 punktow z egzaminu i teraz mam zagwozdke czemu...
Temat dotyczy algorytmow i złożoności :

Stawiam browarek za pomoc

1. Opisz szczegółowo co oznacza w sensie ogólnym zapis O(N2)

2. Jak sądzisz – czy wysokość drzewa binarnych poszukiwań zależy od pierwotnego uprządkowania kluczy przed rozpoczęciem tworzenia tego drzewa ? Odpowiedź szczegółowo uzasadnij.

3. Jak sadzisz – czy algorytm szukania w głąb dla grafu może poprawnie działać w sensie ogólnym, jeśli zastosujemy go do drzewa binarnego ? Dlaczego ?
#programowanie #informatyka

[inny_89]

@FortresMaximus podaj jeszcze te Twoje odpowiedzi to masz szansę wskazania pod razu co zrobiłeś źle

[FortresMaximus]

@inny_89:

1. Jest to zapis odnośnie sortowania babelkowego, jednego z najwolniejszych i najprostszych sortowań które polega na przeiterowaniu po kazdym elemencie i zweryfikowaniu czy liczba jest wieksza badz rowna do porownywanej. Na koniec otrzymujemy z tego ciąg liczb posortowany.
N jest w wzorze ilościa wykonanych przejść

2.Sądzę ze tak, drzewo binarne składa sie z drzewa oraz liści, Dochodzi tutaj do sytuacji w której dane dzielone sa na poddrzewa.
W binarnym drzewie

[FortresMaximus]

@joolekk tu masz

[dedronek]

@FortresMaximus: 1. Tutaj chyba źle bo chodzi bodajże o złożoność obliczeniową do kwadratu co oznacza sytuację, w której masz pętle w pętli

[FortresMaximus]

@dedronek a kojarzysz co moglo byc źle w tych dwóch?

[F.....d]

@FortresMaximus: Notacja Big O równa n^2 nie musi mieć nic wspólnego z Sortowaniem Bąbelkowym. To jest górna granica rzędu funkcji wynosząca n^2. To, że BubbleSort czy InsertSort ma właśnie taką złożoność to bardziej przykłady niż jakieś głębsze powiązanie jednego z drugim.

[F.....d]

@FortresMaximus: Przykładowo wyobraź sobie funkcję w programie wypisującą dane z tablicy dwuwymiarowej. Też będzie miała złożoność n^2. A z sortowaniem bąbelkowym nie ma nic wspólnego.

[dedronek]

@FortresMaximus: niestety znam tylko podstawy z drzew i grafów ( ͡° ʖ̯ ͡°)

[FortresMaximus]

@FMBAlucard czyli odpowiedz @dedronek jest poprawna?

[F.....d]

@FortresMaximus: No tak, O(n2) oznacza górną granicę rzędu złożoności funkcji równą n^2. Czyli jakąś funkcję, która najprawdopodobniej będzie opierała się na dwóch pętlach (jedna zawarta w drugiej) o długości maksymalnej n.

[FortresMaximus]

@FMBAlucard dzieki Miras jakbym mial jeszcze jakieś pytanie mógłbym do Ciebie uderzyc?

[F.....d]

@FortresMaximus: Tak, jeśli będę pamiętał to pomogę. W 1 możesz jako przykłady takich funkcji podać BubbleSort, InsertSort czy SelectSort jak chcesz.

[FortresMaximus]

@FMBAlucard a dlaczego powinno byc okej?

[F.....d]

@FortresMaximus: Twoja odpowiedź do 3 powinna być dobra. To co napisałem tam przy 3 nie ma sensu, bo mi się z szukaniem wszerz pomyliło. X'D

[FortresMaximus]

@FMBAlucard a znas na to odpowiedz?

dpowiedz w jednym zdaniu dlaczego tworząc algorytm musimy określać asercje początkową i końcową algorytmu ?

[F.....d]

@FortresMaximus: Prawdopodobnie, żeby określić czy dla określonych danych wejściowych program powinien się wykonać czy wyrzucić informację o tym, że dane wejściowe są nieprawidłowe albo do obsługi błędów (czy dane wyjściowe chociażby spełniają założenie). Strzelam.

[Hauleth]

@FortresMaximus:

1. Oznacza, że od pewnego n ilość wykonywanych kroków jest zawsze mniejsza niż n^2. Tyle i aż tyle. Przy czym jest to prawdziwe dla dowolnego O(f(n)), które oznacza, że od pewnego n ilość wykonywanych kroków jest zawsze mniejsza niż f(n). Przykładowo O(1) oznacza, że niezależnie od wejścia ilość kroków jest stała, a O(n!) oznacza, że musimy przetestować wszystkie możliwe kombinacje wejścia by uzyskać wynik.
2. Tak, jeśli