Witam! Szukałem, ale nie znalazłem. Jutro mam zaliczenie, a nie rozumiem jednej rzeczy - złożoności obliczeniowej. Konkretnie dla algorytmu Przeszukiwania binarnego( przez połowienie). Wiem, że występuje log i chyba powała, ale co dokładnie, jak mam to pisać na sprawdzianie i jak zapisać? I jak w ogóle określić tą złożoność, na jakiej podstawie [???] ? Bardzo proszę o pomoc doświadczonych ;-)
0
0
no... dzielisz zbior na dwa, potem to, co wyszlo jeszcze na dwa, itd. Czyli masz k operacji dzielenia na 2.
Dla zbioru o poczatkowej licznosci n mozesz miec max. log_2(n) = k operacji dzielenia przez dwa, aby znalezc to, czego szukasz.
Tak mi się wydaje, ale niech ktos to jeszcze zweryfikuje dla pewnosci ;)
0
Rozumiem działanie algorytmu, tylko nie wiem co z tą złożonością :(. Log2n, racja, ale czy tylko to? I czy tak mam to zapisać, bez żadnego opisu, przykładów działań?
0
Przybliży mi ktoś proszę, ten temat, bo mam to na jutro ;/