Proszę wyjaśnić stwierdzenie, że funkcja an + b należy do O (n ^ 2) i Θ (n)?

Powiedzmy, że mam funkcję liniową. f(n)= an+bJaki jest najlepszy sposób na udowodnienie, że ta funkcja należy do O (n ² ) i Θ(n)?

Nie potrzebuję tutaj matematycznego rygoru. Potrzebuję odpowiedzi od programistów. Jakiś logiczny sposób wyjaśnienia.

^{Właśnie dlatego nie opublikowałem pytania w pytaniach matematycznych, a zamiast tego w pytaniach programistów.}

Notacja Big Oh (O, Theta, Omega) dotyczy tempa wzrostu funkcji.

Kiedy implementujesz algorytm, ma on pewną cechę, jak zmienia się środowisko wykonawcze, gdy zwiększasz zestaw danych. Teraz możesz zoptymalizować algorytm, aby działał szybciej o współczynnik 100. Jasne, to świetnie, ale w zasadzie nadal jest to ten sam algorytm. Podobnie za kilka lat komputery mogą być dwa razy szybsze niż obecnie.

Notacja Landaua wyodrębnia te stałe czynniki. Nie ma znaczenia, czy algorytm fjest zawsze dwa razy szybszy niż inny algorytm g: być gmoże można go zoptymalizować tak, aby działał 4 razy szybciej, lub zamiast tego można kupić szybszy sprzęt. Jeśli spojrzysz na to z tej perspektywy, możesz powiedzieć, że są „takie same”. (Nie oznacza to, że możesz (zawsze) ignorować stałe czynniki w praktyce.)

Big oh określa górną granicę, jest podobna do <=relacji.

Zgodzisz się, że 1 < 2to prawda. Czy to oznacza, że 1nie może być mniejsza niż jakakolwiek inna liczba? Zdecydowanie nie. Istnieje nieskończona ilość liczb, które są większe niż 1.

Przy stopach wzrostu jest podobnie. O(n)oznacza zestaw wszystkich funkcji, które rosną liniowo (lub wolniej). O(n^2)z drugiej strony oznacza wszystkie te funkcje, które rosną z kwadratową kompelacją (lub wolniej). Jestem pewien, że zgodzicie się, że funkcja liniowa rośnie wolniej niż funkcja kwadratowa.

Dlatego funkcja może należeć do więcej niż jednej klasy „Big-oh”.

Oto porównanie różnych funkcji z : (z konkretnej matematyki Knutha)

Od lewej do prawej funkcje rosną szybciej.

Oznacza to również, że n ^ 2 rośnie szybciej niż n ^ 1, ponieważ 2> 1.

Definicje

„f rośnie szybciej lub równie szybko jak g”

„f rośnie wolniej lub równie szybko jak g”

Połączenie dwóch powyższych. Mówi, że funkcja frośnie „równie szybko” jak g. To relacja równoważności.

Interpretacja

Powiedzmy, że masz dwa algorytmy fi g.

Omega

Zakładając , oznacza to, że bez względu na budżet nie ma stałej mocy obliczeniowej, którą można by dodać do systemu, tak aby fzawsze działał tak szybko, jak g.

Wielkie och

Zakładając , oznacza to, że jeśli masz wystarczającą ilość danych, fzawsze będzie działać szybciej g, bez względu na to, ile mocy obliczeniowej dodasz do swojego systemu.

Dowód

Jeśli naprawdę próbujesz to udowodnić, musisz pokazać, używając definicji notacji Landaua, że ​​twoja funkcja spełnia niezbędne warunki.

Więc trzeba znaleźć wartości c, d, n_0takie, że warunek jest spełniony.

Oto jak możesz to zrobić dla dolnej granicy za pomocą c:

Ważne jest, aby zdać sobie sprawę, że sam arbitralnie określam, cże jest mniejszy niż a-1jest w porządku. Definicja Theta (g) mówi, że „istnieje c”. Może to być dowolna wartość, o ile jest większa niż 0. (Jeśli ajest to dodatnia liczba rzeczywista, należy jednak nieco zmienić dowód, ponieważ a - 1może być faktycznie ujemny)

(Zakładam, że jestem adodatni, w przeciwnym razie funkcja będzie zawsze ujemna dla dużych wartości n, co nie ma sensu dla funkcji oznaczającej środowisko uruchomieniowe).

Możesz spróbować zrobić to dla górnej granicy, jest dość podobny. Jeśli nie wiesz jak, mogę przedstawić Ci dowód.

Wskazówka: zacznij od d > a + 1

Uwaga

Ważne jest, aby nie udowodnić tego w niewłaściwy sposób. Jeśli założysz, że (an + b) jest w O (n) i stamtąd odejdziesz, nie udowodniłeś, czego chciałeś. Musisz sprawdzić, czy wszystkie twoje kroki idą w obie strony, tzn. Zamiast =>tego <=>.

Kiedy masz do czynienia z wielomianami, dbasz tylko o stopień wielomianu. To znaczy, an + bże zależy ci tylko n. Gdyby tak było an^3 + bn^2 + cn + d, tylko byś się przejmował n^3.

Tak więc zawsze będzie wielomian ze stopniem dΘ(n^d) . Prosty.

Teraz musimy porozmawiać o różnicy między Θ i O. Zasadniczo jest to ta sama różnica co między ==i <=odpowiednio. Więc Θ(n)oznacza, że jest zawsze w zasięgu czynnik stała n. O(n)oznacza, że ​​zawsze mieści się w stałym współczynniku nlub poniżej n.

Oznacza to, że dowolna funkcja Θ(s)dla dowolnego srównież będzie dostępna O(s). Ponadto, jeśli funkcja jest włączona Θ(s)i sjest zawsze mniejsza niż jakaś inna funkcja t, funkcja ta jest włączona, O(t)ale nie Θ(t).

Dla kompletności istnieje również Ω(n). Jeśli Θreprezentuje ==i Oreprezentuje <=, Ωreprezentuje >=. Tak an + bjest Ω(1), Θ(n)i O(n^2).

Jak powiedziałem wcześniej, naprawdę łatwo jest dowiedzieć się, w jakich wielomianach są klasy - wystarczy spojrzeć na stopień. Istnieje również kilka innych funkcji, z którymi można łatwo pracować.

Wszelkie funkcje w formie a^bndla dowolnych ai bsą w Θ(a^n). Dla dowolnej wartości c >= a, są w O(c^n). Każdy wielomian jest w O(2^n). Zasadniczo mówi to tylko, że funkcje wykładnicze zawsze pokonują wielomiany i że podstawa funkcji wykładniczej ma znaczenie.

Logarytmy są odwrotne. Po pierwsze, log_b njest Θ(log n)dla każdego b. Oznacza to, że podstawa nie ma znaczenia dla logarytmów. Ma to sens, ponieważ przełączanie między różnymi zasadami w logarytmach jest po prostu mnożone przez stałą. Funkcje logarytmiczne również są w tym O(n)sensie, że funkcja logarytmiczna jest mniejsza niż jakikolwiek wielomian (co najmniej stopień 1).

Biorąc pod uwagę sumę tych funkcji, największa „wygrywa”. Tak n + log njest, Θ(n)ponieważ ntermin dominuje log n. Mnożenie jest bardziej skomplikowane. W przypadku CS jedyne, co musisz wiedzieć, to to, że nlog njest pomiędzy ni n^2.

Bez użycia dużej matematyki, bierzesz funkcję f (n) = an + b i upuszczasz wszystkie stałe, więc wygląda to tak, że f (n) = n, a następnie bierzesz „n” z najwyższym stopniem jako odpowiedź QED Θ (n)