Mam ten problem, gdzie w klasie mój profesor powiedział, że poniższe oświadczenie jest O(log(n)), gdzie myślałem, że to O(n). Czy ktoś mógłby wyjaśnić, jak to jest O(log(n))?Big O notacji i nie rozumiem z wykładu
Printing a number of magnitude n in binary. Assume that printing each bit requires constant time.
Należy wypracować kilka przykładów. Napisz kilka liczb w systemie binarnym. Na przykład, ile bitów jest w 63, 255 i 511? Zauważ, że liczba bitów nie rośnie tak szybko, jak sama liczba.
To jest O (log (n)), ponieważ musisz podzielić przez 2 za każdym razem, gdy chcesz wydrukować 0 lub 1. Na przykład, aby wydrukować 256 w binarnym, musiałbyś podzielić przez 2, począwszy od 256 i drukować wynik % 2 za każdym razem.
256 % 2 -> 0
64% 2 -> 0
32 % 2 -> 0
16 % 2 -> 0
8 % 2 -> 0
4 % 2 -> 0
2 % 2 -> 0
1 % 2 -> 1
Tak, dla szeregu wielkości 256 trzeba by iteracji 8 czasie, który jest równy log 256.
na przykład, gdybym miał zrobić 7 w binarnym to byłby '7% 2 = 1' następnie podzielić 7 na 2 i byłoby to 3,5, ale jako liczba całkowita jego 3' ' 3% 2 = 1' '1% 2 = 1'' Zatem 7 w binarnym to' 0111', czy to prawda? – Kayracer
Masz rację, wykonano 3 kroki, aby wydrukować każdy bit. Tak, to w przybliżeniu "log 7". – alayor
Słodko, dziękuję – Kayracer
O (log (n)) polega na cięciu danych o połowę. Gdy każdy krok algorytmu wyklucza część z pozostałych danych wejściowych - np. zawsze przecinasz przestrzeń na pół, trzecią, a nawet na 99/100 z poprzedniego kroku - ten algorytm działa w czasie O (log (n)).
nadzieję, że to pomoże
Ile bitów ma liczba 'n', gdy zapisuje się ją w notacji binarnej? Może pomóc przy niektórych przykładach dla małych liczb. –
to jest pytanie i nie ma innych informacji podanych – Kayracer
Więc wypracuj kilka przykładów. Wpisz liczby od 0 do 64 w systemie binarnym. Porównaj samą liczbę z liczbą bitów. –