Najpierw musisz zrozumieć, co to znaczy, że funkcja f (n) jest O (g (n)).
Formalna definicja jest następująca: * Mówi się, że funkcja f (n) jest O (g (n)) iff | f (n) | <= C * | g (n) | ilekroć n> k, gdzie C i k są stałymi. *
niech f (n) = log o podstawie a od n, gdzie a> 1 i g (n) = log o podstawie b z n, gdzie b> 1
UWAGA: Oznacza to, że wartości a i b mogą mieć dowolną wartość większą niż 1, na przykład a = 100 i b = 3
Teraz otrzymujemy: log o podstawie a od n mówi się, że jest O (podstawa log b z n) iff | podstawa loga a z n | <= C * | log o podstawie b z n | kiedykolwiek n> k
Wybierz k = 0 i C = log o podstawie a z b.
Teraz nasze równanie wygląda następująco: | log o podstawie a od n | <= log o podstawie a z b * | log o podstawie b z n | zawsze, gdy n> 0
Zwróć uwagę na prawą stronę, możemy manipulować równaniem: = log o podstawie a z b * | log o podstawie b z n | = | loguj podstawę b z n | * log o podstawie a z b = | log o podstawie a z b ^ (log o podstawie b z n) | = | log o podstawie a n |
Teraz nasze równanie wygląda następująco: | log o podstawie a od n | <= | log o podstawie a n | zawsze, gdy n> 0
Równanie jest zawsze prawdziwe bez względu na wartości n, b lub a, poza ich ograniczeniami a, b> 1 i n> 0. Zatem logarytm o podstawie a od n wynosi O (o podstawie b od n), a ponieważ a, b nie ma znaczenia, możemy je po prostu pominąć.
Możesz zobaczyć wideo na YouTube tutaj: https://www.youtube.com/watch?v=MY-VCrQCaVw
Możesz przeczytać artykuł na ten temat tutaj: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca
log n
, ma na myśli logarytm naturalny. 2. Kiedy informatyk pisze,log n
ma na myśli podstawę dwa. 3. Kiedy inżynier piszelog n
, ma na myśli dziesiątkę. Są to zwykle prawdziwe.