Square Root (Integer)

Q: Jaka jest złożoność czasowa wyszukiwania binarnego pierwiastka kwadratowego?

Czas O(log x) i pamięć O(1) . Każdy krok zmniejsza zakres kandydatów o połowę, więc dla x = 2^31 - 1 potrzeba 31 kroków. Zliczanie w górę od 0 wymaga O(√x) kroków — 46340 dla tego samego x — co w tym przypadku jest w porządku, ale liczba kroków szybko rośnie przy danych wejściowych 64-bitowych.

Q: Jak metoda Newtona oblicza całkowity pierwiastek kwadratowy?

Zacznij od r = x . Dopóki r × r > x , zastępuj r wartością (r + x / r) / 2 , używając dzielenia całkowitego. Każdy krok zmniejsza r w kierunku pierwiastka, nie przekraczając go, a pętla kończy się na zaokrąglonym w dół pierwiastku kwadratowym. Dla x = 2^31 - 1 potrzeba 19 kroków, a liczba poprawnych cyfr mniej więcej podwaja się z każdym krokiem, gdy wynik jest już bliski pierwiastka.

ŁatweWyszukiwanie binarne Matematyka i symulacja

+10

Twoja funkcja otrzymuje nieujemną liczbę całkowitą x i zwraca jej całkowity pierwiastek kwadratowy: największą liczbę całkowitą r, dla której r × r ≤ x. Innymi słowy, pierwiastek jest zaokrąglany w dół, więc dla liczby, która nie jest kwadratem liczby całkowitej, zwracany jest pierwiastek z najbliższego mniejszego kwadratu liczby całkowitej. Oblicz go samodzielnie, bez używania wbudowanej funkcji pierwiastka kwadratowego ani potęgowania.

Funkcja

mySqrt(x: integer) → integer

xinteger: nieujemna liczba całkowita, z której należy wyciągnąć pierwiastek kwadratowy
Zwracainteger: pierwiastek kwadratowy z x zaokrąglony w dół do liczby całkowitej

Ograniczenia

0 ≤ x ≤ 2³¹ - 1
Nie wywołuj wbudowanej funkcji pierwiastka kwadratowego, potęgowania ani funkcji wykładniczej.

Przykłady

Wejście: x = 17
Wyjście: 4
Wyjaśnienie: 4 × 4 = 16 to maksymalnie 17, ale 5 × 5 = 25 to więcej, więc pierwiastek z 17 zaokrągla się w dół do 4.

Wejście: x = 49
Wyjście: 7
Wyjaśnienie: 49 jest kwadratem doskonałym, 7 × 7 = 49, więc nic nie jest zaokrąglane, a odpowiedź wynosi dokładnie 7.

+17 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak zamiast tego znaleźć całkowity pierwiastek sześcienny, czyli największą wartość r, dla której r × r × r ≤ x, jeśli x może być również ujemne?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Zliczanie w górę od 0, aż kolejny kwadrat przekroczy x, daje poprawną odpowiedź, ale wymaga jednego kroku na każdą jednostkę pierwiastka, czyli około 46000 kroków w górnej części zakresu. Kwadraty 0, 1, 4, 9, 16 i tak dalej są uporządkowane, więc możesz użyć wyszukiwania binarnego, aby znaleźć ostatnią wartość, której kwadrat jest nie większy niż x, i zakończyć w około 31 krokach. Pułapką w obu przypadkach jest przepełnienie: kwadrat wartości kandydującej nie zawsze mieści się w 32 bitach.

Odliczaj w górę od zera

Intuicja

Pierwiastek to największe r, dla którego r × r ≤ x. Zacznij od r = 0, którego kwadrat zawsze mieści się w zakresie, i zwiększaj r o 1, dopóki kwadrat następnej liczby nadal się mieści. Pętla kończy się przy pierwszym r, którego następnik jest za duży — to właśnie pierwiastek. Dla x = 17 mieszczą się kwadraty 1, 4, 9 i 16, a 25 już nie, więc pętla kończy się na 4.

Pętla wykonuje się raz na każdą jednostkę wyniku. Największy wynik w tym przypadku to 46340, więc pętla wykona najwyżej 46340 kroków, co zajmuje niewiele czasu. Koszt wynosi jednak O(√x) i rośnie wraz z wartością wejściową: dla 64-bitowego x obliczenia mogą wymagać około 3 × 10^9 kroków.

Zwróć uwagę na ostatnie sprawdzenie. Dla x = 2^31 - 1 pętla podnosi 46341 do kwadratu, aby sprawdzić, że wynik jest za duży, a 46341 × 46341 = 2147488281 nie mieści się w 32-bitowej liczbie całkowitej. Obliczaj kwadrat w 64 bitach.

Algorytm

Ustaw root = 0.
Gdy (root + 1) × (root + 1) ≤ x, zwiększ root o 1.
Zwróć root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Wyszukiwanie binarne odpowiedzi

Intuicja

Ustaw kandydatów 0, 1, 2, aż do x, i zadaj każdemu z nich to samo pytanie: czy jego kwadrat jest nie większy niż x? Odpowiedzi to kolejno tak, tak, tak, a potem nie dla każdego kandydata za pierwiastkiem, ponieważ kwadraty tylko rosną. Pierwiastek to ostatnia odpowiedź „tak”. Wyszukiwanie binarne służy właśnie do przeszukiwania uporządkowanego ciągu odpowiedzi „tak”, po których następują odpowiedzi „nie”.

Przechowuj zakres kandydatów od lo do hi, których jeszcze nie rozstrzygnięto, początkowo od 0 do x, oraz zmienną best oznaczającą największą dotychczasową wartość, dla której odpowiedź brzmi „tak”. Sprawdź środkową wartość mid. Jeśli mid × mid ≤ x, pierwiastek jest równy mid lub większy: zapisz tę wartość w best i przesuń lo na mid + 1. W przeciwnym razie pierwiastek jest mniejszy: przesuń hi na mid - 1. Gdy zakres będzie pusty, best będzie pierwiastkiem.

Prześledźmy x = 17. W zakresie od 0 do 17 sprawdzamy 8 (64, za dużo), potem w zakresie od 0 do 7 sprawdzamy 3 (9, pasuje, best = 3), następnie w zakresie od 4 do 7 sprawdzamy 5 (25, za dużo), a potem w zakresie od 4 do 4 sprawdzamy 4 (16, pasuje, best = 4). Zakres jest pusty, a odpowiedź to 4. Każdy krok zmniejsza zakres o połowę, więc dla x = 2^31 - 1 potrzeba 31 kroków. Wykonuj mnożenie w 64 bitach: pierwsza wartość mid wynosi wtedy 1073741823.

Algorytm

Ustaw lo = 0, hi = x i best = 0.
Dopóki lo ≤ hi, oblicz mid, środek zakresu.
Jeśli mid × mid ≤ x (w 64 bitach), ustaw best = mid i lo = mid + 1.
W przeciwnym razie ustaw hi = mid - 1.
Zwróć best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Pułapki i przypadki brzegowe

Samo wyszukiwanie jest krótkie; błędy kryją się w działaniach arytmetycznych i przypadkach brzegowych.

Podnoszenie do kwadratu w 32 bitach. Dla x = 2147483647 pierwszy kandydat na środek to 1073741823, a jego kwadrat wynosi około 1.15 × 10^18. W 32-bitowym int wartość zawija się do błędnego wyniku, który może nawet wyglądać na wystarczająco mały. Wykonuj mnożenie w 64 bitach albo zamiast tego porównuj m ≤ x / m.
Podnoszenie do kwadratu następnego kandydata w 32 bitach w pętli zliczającej. Pierwiastek z 2^31 - 1 wynosi 46340, a ostatnie sprawdzenie w pętli podnosi do kwadratu 46341, co daje 2147488281 — wartość powyżej limitu 32 bitów.
Przekroczenie zakresu 32 bitów. Wyłączna górna granica hi = x + 1 wynosi 2147483648 dla największego x, czyli o jeden więcej niż limit 32 bitów. Przy włącznie górnej granicy hi = x, lo + hi osiąga dokładnie 2147483647 w pierwszym kroku, więc mieści się bez żadnego zapasu. Używaj indeksów 64-bitowych albo lo + (hi - lo) / 2.
Zwracanie ostatniego sprawdzonego mid zamiast ostatniego, który pasował. Dla x = 17 wyszukiwanie kończy się po sprawdzeniu 5, które jest za duże; odpowiedzią jest zapamiętana wartość 4.
Psucie obsługi małych przypadków. Wyszukiwanie rozpoczynające się od lo = 1 pomija x = 0, a sprawdzenie przez dzielenie m ≤ x / m powoduje dzielenie przez zero, gdy m = 0. Sprawdź osobno 0 i 1.

Najczęstsze pytania4

Jak obliczyć pierwiastek kwadratowy bez wbudowanej funkcji?

Aby obliczyć całkowity pierwiastek kwadratowy, zastosuj wyszukiwanie binarne. Kandydaci od 0 do x dzielą się na ciąg, którego kwadraty są nie większe niż x, oraz ciąg, którego kwadraty są większe. Wyszukiwanie binarne znajduje ostatniego kandydata z pierwszego ciągu. Innym popularnym rozwiązaniem jest metoda Newtona: iteracyjnie poprawia przybliżenie r za pomocą (r + x / r) / 2, aż kwadrat będzie pasował.

Jaka jest złożoność czasowa wyszukiwania binarnego pierwiastka kwadratowego?

Czas O(log x) i pamięć O(1). Każdy krok zmniejsza zakres kandydatów o połowę, więc dla x = 2^31 - 1 potrzeba 31 kroków. Zliczanie w górę od 0 wymaga O(√x) kroków — 46340 dla tego samego x — co w tym przypadku jest w porządku, ale liczba kroków szybko rośnie przy danych wejściowych 64-bitowych.

Jak metoda Newtona oblicza całkowity pierwiastek kwadratowy?

Zacznij od r = x. Dopóki r × r > x, zastępuj r wartością (r + x / r) / 2, używając dzielenia całkowitego. Każdy krok zmniejsza r w kierunku pierwiastka, nie przekraczając go, a pętla kończy się na zaokrąglonym w dół pierwiastku kwadratowym. Dla x = 2^31 - 1 potrzeba 19 kroków, a liczba poprawnych cyfr mniej więcej podwaja się z każdym krokiem, gdy wynik jest już bliski pierwiastka.

Dlaczego rozwiązanie wymaga liczb całkowitych 64-bitowych, skoro wynik mieści się w 32 bitach?

Odpowiedź wynosi co najwyżej 46340, ale testowane przez Ciebie kandydaty już nie. Wyszukiwanie binarne w przedziale od 0 do x najpierw sprawdza kandydata bliskiego 10^9, a jego kwadrat jest bliski 10^18, czyli znacznie przekracza limit 32-bitowy wynoszący około 2.1 × 10^9. Podnoszenie do kwadratu na 64 bitach pozwala zachować dokładność porównania. Porównanie m ≤ x / m pozwala całkowicie uniknąć dużego iloczynu.