Divide And Conquer

Question 1

Do czego wykorzystywana jest technika divide and conquer?

Answer 1

Do rozwiazywania rozmaitych zadanań

Question 2

Jaki jest pierwszy poważny algorytm z typu dziel i rządź?

Answer 2

Quicksort - algorytm sortowania który charakteryzuje się znacznie większą szybkością niż sortowanie przez wybieranie

Question 3

Jak znaleźć największy kożliwy rozmiar kwadartu do podzielenia kawałka ziemi na równe części?

Answer 3

Najlepiej skorzystać z dziel i rządź

Question 4

Z jakich części składa się rozwiązanie problemu metodą dziel i rządź?

Answer 4

1) Określenie przypadku podstawowego który powinien być najprostszym możliwym przypadkiem
2) Dzielenie lub redukowanie problemu aż do sprawdzenia go do przypadku podstawowego

Question 5

Wyszukiwanie binarne to algorytm typu?

Answer 5

Dziel i rządź

Question 6

Jaki jest przypadek bazowy dla wyszukiwania binarnego?

Answer 6

Przypadek bazowy - to tablica zawierająca jeden element , jeżeli szukany element jest taki sam jak ten który znajduje się w tablicy to go znajdziemy. W przeciwnym wypadku szukanego elementu nie ma w strukturze.

Question 7

Jaki jest przypadek rekurencyjny wyszukiwania binarnego?

Answer 7

Tablicę dzieli się na pół jedną połowę się odrzucani wywołuje się wyszukiwanie binarne na drugiej

Question 8

How quicksort works ?

Answer 8

Pick an element, called a pivot, from the array.
Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Question 9

What is a pivot?

Answer 9

Element osiowy -wybrany element z tablicy

Question 10

W strategii dziel i rządz co robimy?

Answer 10

Dzielimy tablicę aż do osiągnięcia przypadku podstawowego

Question 11

Co to dowód indukcyjny?

Answer 11

Jest to jedna z metod by udowodnić że algorytm działa. Sklada się on z przypadku podstawowego i indukcyjnego.

Podstawowy - jesli wejde na szczebel pierwszy to znaczy ze na drugi tez

Indukcyjny - jesli nogi znajduja sie na jakims szczeblu to znaczy ze moge je postawic na nastepnym szczeblu

Question 12

Co tak nalrawde oznacza notacja O(n)?

Answer 12

C*n

Paramert c oznacza stala ilosc czasu wykorzystywana orzez algorytm

Czyli 10*n