Moja wiedza na temat big-O jest ograniczona, a kiedy logi logiczne pojawiają się w równaniu, wytrącają mnie jeszcze bardziej.

Czy ktoś może mi wyjaśnić w prostych słowach, czym jest O(log n)algorytm? Skąd pochodzi logarytm?

Pojawiło się to szczególnie, gdy próbowałem rozwiązać to pytanie praktyczne w połowie semestru:

Niech X (1..n) i Y (1..n) zawierają dwie listy liczb całkowitych, każda posortowana w kolejności nie malejącej. Podaj algorytm czasu O (log n), aby znaleźć medianę (lub n-tą najmniejszą liczbę całkowitą) wszystkich 2n połączonych elementów. Na przykład X = (4, 5, 7, 8, 9) i Y = (3, 5, 8, 9, 10), to 7 jest medianą połączonej listy (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [Wskazówka: użyj koncepcji wyszukiwania binarnego]

Muszę się zgodzić, że to dość dziwne, gdy po raz pierwszy widzisz algorytm O (log n) ... skąd u licha pochodzi ten logarytm? Okazuje się jednak, że istnieje kilka różnych sposobów na wyświetlenie terminu dziennika w notacji duże-O. Tu jest kilka:

Wielokrotne dzielenie przez stałą

Weź dowolną liczbę n; powiedz, 16. Ile razy możesz podzielić n przez dwa, zanim otrzymasz liczbę mniejszą lub równą jeden? Mamy to dla 16 lat

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Zauważ, że kończy się to na czterech krokach. Co ciekawe, mamy również ten log ₂ 16 = 4. Hmmm ... a co ze 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

Wymagało to siedmiu kroków i log ₂ 128 = 7. Czy to zbieg okoliczności? Nie! Jest ku temu dobry powód. Załóżmy, że dzielimy liczbę n przez 2 i razy. Wtedy otrzymujemy liczbę n / 2 ⁱ . Jeśli chcemy obliczyć wartość i, gdzie ta wartość wynosi co najwyżej 1, otrzymujemy

n / 2 ⁱ ≤ 1

n ≤ 2 ⁱ

log ₂ n ≤ w

Innymi słowy, jeśli wybierzemy liczbę całkowitą i taką, że i ≥ log ₂ n, to po podzieleniu n na pół i razy otrzymamy wartość, która wynosi najwyżej 1. Najmniejsze i, dla którego jest to gwarantowane, to z grubsza log ₂ n, więc jeśli mamy algorytm, który dzieli przez 2, aż liczba stanie się wystarczająco mała, wówczas możemy powiedzieć, że kończy się O (log n) krokami.

Ważnym szczegółem jest to, że nie ma znaczenia, przez jaką stałą dzielisz n (o ile jest większa niż jeden); jeśli podzielisz przez stałą k, osiągnięcie liczby 1 zajmie log _k n kroków. Zatem każdy algorytm, który wielokrotnie dzieli rozmiar wejściowy przez pewien ułamek, będzie wymagał O (log n) iteracji do zakończenia. Te iteracje mogą zająć dużo czasu, więc czas wykonania netto nie musi wynosić O (log n), ale liczba kroków będzie logarytmiczna.

Więc gdzie to się dzieje? Jednym z klasycznych przykładów jest wyszukiwanie binarne , szybki algorytm wyszukiwania wartości w posortowanej tablicy. Algorytm działa w ten sposób:

• Jeśli tablica jest pusta, zwróć, że elementu nie ma w tablicy.
• Inaczej:
  • Spójrz na środkowy element tablicy.
  • Jeśli jest równy elementowi, którego szukamy, zwróć sukces.
  • Jeśli jest większy niż element, którego szukamy:
    • Wyrzuć drugą połowę tablicy.
    • Powtarzać
  • Jeśli jest mniejszy niż element, którego szukamy:
    • Wyrzuć pierwszą połowę tablicy.
    • Powtarzać

Na przykład, aby wyszukać 5 w tablicy

1   3   5   7   9   11   13

Najpierw przyjrzymy się środkowemu elementowi:

1   3   5   7   9   11   13
            ^

Ponieważ 7> 5, a tablica jest posortowana, wiemy na pewno, że liczba 5 nie może znajdować się w tylnej połowie tablicy, więc możemy ją po prostu odrzucić. To odchodzi

1   3   5

Spójrzmy teraz na środkowy element tutaj:

1   3   5
    ^

Ponieważ 3 <5, wiemy, że 5 nie może pojawić się w pierwszej połowie tablicy, więc możemy wrzucić pierwszą połowę tablicy, aby wyjść

        5

Ponownie patrzymy na środek tej tablicy:

        5
        ^

Ponieważ jest to dokładnie ta liczba, której szukamy, możemy zgłosić, że w tablicy rzeczywiście znajduje się 5.

Więc jak wydajne jest to? Cóż, przy każdej iteracji wyrzucamy co najmniej połowę pozostałych elementów tablicy. Algorytm zatrzymuje się, gdy tablica jest pusta lub gdy znajdziemy żądaną wartość. W najgorszym przypadku elementu nie ma, więc zmniejszamy o połowę rozmiar tablicy, aż skończą się elementy. Jak długo to trwa? Cóż, ponieważ w kółko przecinamy tablicę na pół, wykonamy co najwyżej O (log n) iteracji, ponieważ nie możemy przeciąć tablicy o połowę więcej niż O (log n) razy przed uruchomieniem poza elementami tablicy.

Algorytmy stosujące ogólną technikę dziel i rządź (dzielenie problemu na części, rozwiązywanie tych części, a następnie składanie go z powrotem) mają tendencję do posiadania wyrażeń logarytmicznych z tego samego powodu - nie możesz dalej przecinać jakiegoś obiektu pół więcej niż O (log n) razy. Możesz spojrzeć na sortowanie przez scalanie jako świetny przykład tego.

Przetwarzanie wartości po jednej cyfrze na raz

Ile cyfr składa się z liczby n o podstawie 10? Cóż, jeśli liczba zawiera k cyfr, wówczas największa cyfra jest wielokrotnością 10 ^tys . Największa liczba k-cyfr to 999 ... 9, k razy, a to jest równe 10 ^{k + 1} - 1. W konsekwencji, jeśli wiemy, że n ma w sobie k cyfr, to wiemy, że wartość n wynosi co najwyżej 10 ^{k + 1} - 1. Jeśli chcemy obliczyć k na podstawie n, otrzymamy

n ≤ 10 ^{k + 1} - 1

n + 1 ≤ 10 ^{k + 1}

log ₁₀ (n + 1) ≤ k + 1

(log ₁₀ (n + 1)) - 1 ≤ k

Z którego otrzymujemy, że k jest w przybliżeniu logarytmem o podstawie 10 z n. Innymi słowy, liczba cyfr w n wynosi O (log n).

Na przykład pomyślmy o złożoności dodawania dwóch dużych liczb, które są zbyt duże, aby pasowały do ​​słowa maszynowego. Załóżmy, że mamy te liczby reprezentowane przez podstawę 10 i nazwiemy liczby m i n. Jednym ze sposobów ich dodawania jest metoda podstawowa - zapisuj liczby po jednej cyfrze, a następnie pracuj od prawej do lewej. Na przykład, aby dodać 1337 i 2065, zaczniemy od zapisania liczb jako

    1  3  3  7
+   2  0  6  5
==============

Dodajemy ostatnią cyfrę i przenosimy 1:

          1
    1  3  3  7
+   2  0  6  5
==============
             2

Następnie dodajemy przedostatnią („przedostatnią”) cyfrę i przenosimy 1:

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

Następnie dodajemy przedostatnią („antepenultimate”) cyfrę:

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

Na koniec dodajemy przedostatnią cyfrę („preantepenultimate”… Uwielbiam angielski):

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

Ile pracy wykonaliśmy? W sumie wykonujemy O (1) pracy na cyfrę (czyli stałą ilość pracy), a jest O (max {log n, log m}) wszystkich cyfr, które muszą zostać przetworzone. Daje to w sumie złożoność O (max {log n, log m}), ponieważ musimy odwiedzić każdą cyfrę w dwóch liczbach.

Wiele algorytmów otrzymuje w nich człon O (log n), pracując po jednej cyfrze w jakiejś bazie. Klasycznym przykładem jest sortowanie radix , które sortuje liczby całkowite po jednej cyfrze. Istnieje wiele odmian sortowania radix, ale zwykle działają one w czasie O (n log U), gdzie U jest największą możliwą liczbą całkowitą, która jest sortowana. Powodem tego jest to, że każdy przebieg sortowania zajmuje O (n) czasu, a do przetworzenia każdej z O (log U) cyfr największej sortowanej liczby wymagane jest łącznie O (log U) iteracji. Wiele zaawansowanych algorytmów, takich jak algorytm najkrótszej ścieżki Gabowa lub skalująca wersja algorytmu maksymalnego przepływu Forda-Fulkersona , ma złożoność logarytmiczną, ponieważ działają one po jednej cyfrze na raz.

Jeśli chodzi o drugie pytanie dotyczące sposobu rozwiązania tego problemu, warto przyjrzeć się temu pokrewnemu pytaniu, które dotyczy bardziej zaawansowanej aplikacji. Biorąc pod uwagę ogólną strukturę problemów, które są tutaj opisane, możesz teraz lepiej myśleć o problemach, gdy wiesz, że w wyniku znajduje się termin dziennika, więc radziłbym nie patrzeć na odpowiedź, dopóki jej nie podasz jakaś myśl.

Mam nadzieję że to pomoże!

Kiedy mówimy o opisach big-Oh, zwykle mówimy o czasie potrzebnym do rozwiązania problemów o danej wielkości . Zwykle w przypadku prostych problemów rozmiar ten charakteryzuje się po prostu liczbą elementów wejściowych i zwykle nazywa się to n lub N. (Oczywiście nie zawsze jest to prawdą - problemy z wykresami są często charakteryzowane liczbą wierzchołków, V i liczba krawędzi, E; ale na razie porozmawiamy o listach obiektów, z N obiektami na listach).

Mówimy, że problem „jest duży-Oh (jakaś funkcja N)” wtedy i tylko wtedy, gdy :

Dla wszystkich N> jakiegoś dowolnego N_0, istnieje pewna stała c, taka że czas działania algorytmu jest mniejszy niż ta stała c razy (pewna funkcja N.)

Innymi słowy, nie myśl o małych problemach, w których liczy się „stały koszt” ustawiania problemu, myśl o dużych problemach. A kiedy myśli o wielkich problemach, big-OH (niektóre funkcja N) oznacza, że run-time jest jeszcze zawsze mniej niż kilka razy stałych że funkcja. Zawsze.

Krótko mówiąc, funkcja ta jest górną granicą, aż do stałego współczynnika.

Zatem „duże-Oh z log (n)” oznacza to samo, co powiedziałem powyżej, z tym że „pewna funkcja N” jest zastąpiona przez „log (n)”.

Więc twój problem każe ci pomyśleć o wyszukiwaniu binarnym, więc pomyślmy o tym. Załóżmy, że masz, powiedzmy, listę N elementów posortowanych w kolejności rosnącej. Chcesz się dowiedzieć, czy jakaś podana liczba znajduje się na tej liście. Jednym ze sposobów na to, co nie jest wyszukiwaniem binarnym, jest po prostu przeskanowanie każdego elementu listy i sprawdzenie, czy jest to Twój numer docelowy. Możesz mieć szczęście i znaleźć go za pierwszym razem. Ale w najgorszym przypadku sprawdzisz N różnych razy. To nie jest wyszukiwanie binarne i nie jest duże-Oh z log (N), ponieważ nie ma sposobu, aby wymusić je w kryteriach, które naszkicowaliśmy powyżej.

Możesz wybrać dowolną stałą c = 10, a jeśli twoja lista ma N = 32 elementy, wszystko jest w porządku: 10 * log (32) = 50, czyli więcej niż czas wykonania 32. Ale jeśli N = 64 , 10 * log (64) = 60, czyli mniej niż w czasie wykonywania 64. Możesz wybrać c = 100, 1000 lub gazillion, a nadal będziesz w stanie znaleźć trochę N, które narusza ten wymóg. Innymi słowy, nie ma N_0.

Jeśli jednak przeprowadzamy wyszukiwanie binarne, wybieramy środkowy element i dokonujemy porównania. Następnie wyrzucamy połowę liczb i robimy to jeszcze raz i jeszcze raz, i tak dalej. Jeśli twój N = 32, możesz to zrobić tylko około 5 razy, czyli log (32). Jeżeli Państwa N = 64, można to zrobić tylko około 6 razy, itd. Teraz można wybrać tę dowolną stałą c, w taki sposób, że wymóg jest zawsze spełnione w przypadku dużych wartości N.

Mając to wszystko na uwadze, O (log (N)) zwykle oznacza to, że masz jakiś sposób na zrobienie prostej rzeczy, która zmniejsza rozmiar twojego problemu o połowę. Podobnie jak w przypadku wyszukiwania binarnego powyżej. Gdy przekroisz problem na pół, możesz go przeciąć jeszcze raz i jeszcze raz. Ale, co najważniejsze, nie możesz zrobić jakiegoś kroku przetwarzania wstępnego, który zająłby więcej czasu niż ten czas O (log (N)). Na przykład nie możesz przetasować swoich dwóch list w jedną dużą listę, chyba że znajdziesz sposób, aby to zrobić również w czasie O (log (N)).

(UWAGA: Prawie zawsze Log (N) oznacza log-podstawa-dwa, co zakładam powyżej).

W poniższym rozwiązaniu wszystkie wiersze z wywołaniem rekurencyjnym są wykonywane na połowie podanych rozmiarów tablic podrzędnych X i Y. Pozostałe wiersze są wykonywane w stałym czasie. Funkcja rekurencyjna to T (2n) = T (2n / 2) + c = T (n) + c = O (lg (2n)) = O (lgn).

Zaczynasz od MEDIANA (X, 1, n, Y, 1, n).

MEDIAN(X, p, r, Y, i, k) 
if X[r]<Y[i]
    return X[r]
if Y[k]<X[p]
    return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
    if X[q+1]>Y[j] and Y[j+1]>X[q]
        if X[q]>Y[j]
            return X[q]
        else
            return Y[j]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q+1, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j+1, k)
else
    if X[q]>Y[j] and Y[j+1]>X[q-1]
        return Y[j]
    if Y[j]>X[q] and X[q+1]>Y[j-1]
        return X[q]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j, k)

Termin dziennika pojawia się bardzo często w analizie złożoności algorytmu. Oto kilka wyjaśnień:

1. Jak reprezentujesz liczbę?

Weźmy liczbę X = 245436. Ta notacja „245436” zawiera ukrytą informację. Wyraźnie przedstawiając te informacje:

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0

Co jest dziesiętnym rozszerzeniem liczby. Tak więc minimalna ilość informacji potrzebnych do przedstawienia tej liczby to 6 cyfr. To nie przypadek, ponieważ każda liczba mniejsza niż 10 ^ d może być reprezentowana przez d cyfr.

Ile cyfr jest potrzebnych do reprezentowania X? To jest równe największemu wykładnikowi 10 w X plus 1.

==> 10 ^ d> X
==> log (10 ^ d)> log (X)
==> d * log (10)> log (X)
==> d> log (X) // Pojawia się log ponownie ...
==> d = podłoga (log (x)) + 1

Zauważ również, że jest to najbardziej zwięzły sposób określenia liczby w tym zakresie. Każda redukcja doprowadzi do utraty informacji, ponieważ brakującą cyfrę można przypisać do 10 innych liczb. Na przykład: 12 * można odwzorować na 120, 121, 122,…, 129.

2. Jak szukać liczby w (0, N - 1)?

Przyjmując N = 10 ^ d, posługujemy się naszą najważniejszą obserwacją:

Minimalna ilość informacji umożliwiająca jednoznaczną identyfikację wartości w zakresie od 0 do N - 1 = log (N) cyfr.

Oznacza to, że gdy poprosimy o wyszukanie liczby w wierszu całkowitoliczbowym, z zakresu od 0 do N - 1, potrzebujemy przynajmniej log (N) próby jej znalezienia. Czemu? Każdy algorytm wyszukiwania będzie musiał podczas wyszukiwania numeru wybierać jedną cyfrę po drugiej.

Minimalna liczba cyfr, które musi wybrać, to log (N). Stąd minimalna liczba operacji potrzebnych do wyszukania liczby w przestrzeni o rozmiarze N to log (N).

Czy potrafisz odgadnąć złożoność kolejności wyszukiwania binarnego, wyszukiwania trójskładnikowego lub wyszukiwania deca?
Jego O (log (N))!

3. Jak sortujesz zbiór liczb?

Kiedy zostaniesz poproszony o posortowanie zbioru liczb A w tablicę B, oto jak to wygląda ->

Permute Elements

Każdy element w oryginalnej tablicy musi być odwzorowany na odpowiadający mu indeks w posortowanej tablicy. Zatem dla pierwszego elementu mamy n pozycji. Aby poprawnie znaleźć odpowiedni indeks w tym zakresie od 0 do n - 1, potrzebujemy… log (n) operacji.

Następny element wymaga operacji log (n-1), następny log (n-2) i tak dalej. Suma wyniesie:

==> log (n) + log (n - 1) + log (n - 2) +… + log (1)

Korzystanie z log (a) + log (b) = log (a * b),

==> log (n!)

Można to przybliżyć do nlog (n) - n.
Co to jest O (n * log (n))!

Dlatego dochodzimy do wniosku, że nie może być algorytmu sortowania, który byłby lepszy niż O (n * log (n)). Niektóre algorytmy o takiej złożoności to popularne sortowanie przez scalanie i sortowanie na stosie!

Oto niektóre z powodów, dla których log (n) pojawia się tak często w analizie złożoności algorytmów. To samo można rozszerzyć na liczby binarne. Nakręciłem tutaj film o tym.
Dlaczego log (n) pojawia się tak często podczas analizy złożoności algorytmu?

Twoje zdrowie!

Złożoność czasową O (log n) nazywamy, gdy rozwiązanie jest oparte na iteracjach po n, gdzie praca wykonana w każdej iteracji jest ułamkiem poprzedniej iteracji, ponieważ algorytm pracuje w kierunku rozwiązania.

Nie mogę jeszcze komentować ... To jest nekro! Odpowiedź Avi Cohena jest nieprawidłowa, spróbuj:

X = 1 3 4 5 8
Y = 2 5 6 7 9

Żaden z warunków nie jest spełniony, więc MEDIAN (X, p, q, Y, j, k) odetnie obie piątki. Są to sekwencje niezmniejszające się, nie wszystkie wartości są różne.

Wypróbuj również ten przykład o parzystej długości z różnymi wartościami:

X = 1 3 4 7
Y = 2 5 6 8

Teraz MEDIAN (X, p, q, Y, j + 1, k) odetnie cztery.

Zamiast tego oferuję ten algorytm, nazwij go MEDIANEM (1, n, 1, n):

MEDIAN(startx, endx, starty, endy){
  if (startx == endx)
    return min(X[startx], y[starty])
  odd = (startx + endx) % 2     //0 if even, 1 if odd
  m = (startx+endx - odd)/2
  n = (starty+endy - odd)/2
  x = X[m]
  y = Y[n]
  if x == y
    //then there are n-2{+1} total elements smaller than or equal to both x and y
    //so this value is the nth smallest
    //we have found the median.
    return x
  if (x < y)
    //if we remove some numbers smaller then the median,
    //and remove the same amount of numbers bigger than the median,
    //the median will not change
    //we know the elements before x are smaller than the median,
    //and the elements after y are bigger than the median,
    //so we discard these and continue the search:
    return MEDIAN(m, endx, starty, n + 1 - odd)
  else  (x > y)
    return MEDIAN(startx, m + 1 - odd, n, endy)
}