Czy funkcje są zawsze asymptotycznie porównywalne?

Kiedy porównujemy złożoność dwóch algorytmów, zwykle dzieje się tak, że albo albo g ( n ) = O ( f ( n ) ) (ewentualnie oba), gdzie f i g to czasy działania (na przykład) dwóch algorytmów.$f(n) = O(g(n))$$g(n) = O(f(n))$$f$$g$

Czy tak jest zawsze? Oznacza to, że ma co najmniej jeden ze związków i g ( n ) = O ( f ( n ) ) zawsze utrzymywać, że jest ogólnie funkcji f , g ? Jeśli nie, jakie założenia musimy przyjąć i (dlaczego) jest ok, kiedy mówimy o czasach działania algorytmu?$f(n) = O(g(n))$$g(n) = O(f(n))$$f$$g$

Nie każda para funkcji jest porównywalna z notacją ; pod funkcji f ( n ) = n i g ( n ) = { 1 , gdy  n  jest liczbą nieparzystą , n 2 , gdy  n  jest nawet . Co więcej, funkcje takie jak g ( n ) faktycznie powstają jako czasy działania algorytmów. Rozważ oczywisty algorytm brute-force, aby ustalić, czy dana liczba całkowita n jest liczbą pierwszą:$O(\cdot)$$f(n) = n$

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

Algorytm ten wymaga operacji arytmetycznych gdy n jest parzyste, O ( $\Theta(1)$$n$operacje, gdynjest złożone, aleΘ(n)operacje, gdynjest liczbą pierwszą. Zatem formalnie algorytm ten jestnieporównywalnyz algorytmem wykorzystującym$O(\sqrt{n})$$n$$\Theta(n)$$n$ operacji arytmetycznych dlakażdegon.$\sqrt{n}$ $n$

W większości przypadków, gdy analizujemy algorytmy, chcemy jedynie asymptotycznej górnej granicy formy dla pewnej stosunkowo prostej funkcji f . Na przykład większość podręczników po prostu (i poprawnie) raportuje, że działa w operacjach arytmetycznych O ( n ) . Typowe górne granice funkcji są iloczynami wykładników, wielomianów i logarytmów (chociaż czasami pojawiają się bardziej egzotyczne bestie, takie jak silnia i logarytmy iterowane ). Nietrudno udowodnić, że dowolne dwie takie funkcje są porównywalne.$O(f(n))$$f$IsPrime(n)$O(n)$

Zobacz także to pytanie MathOverflow .

Z wikipedii, definicja dużej notacji O:

wtedy i tylko wtedy, gdy istnieje dodatnia stała M taka, że ​​dla wszystkich wystarczająco dużych wartości , f ( x ) jest co najwyżej M pomnożone przez g ( x ) w wartości bezwzględnej. To znaczy, f ( x ) ∈ O ( g ( x ) ) wtedy i tylko wtedy, gdy istnieje dodatnia liczba rzeczywista M i liczba rzeczywista x 0 taka, że$x$$f(x)$$g(x)$$f(x) \in O(g(x))$$M$$x_0$

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

Co dzieje się w przypadku funkcji, które nie są zbieżne (do stałej ani do nieskończoności)?

Spójrz na funkcje oraz g ( x ) = $f(x) = |xsin(x)|$$g(x) = 10$

$x_0$$x > x0$$x = k\pi$$f(x) = 0$$M$$Mf(x) > g(x)$$g(x) \; \not\in O(f(x))$

$|xsin(x)|$$M$$x_0$$x > x_0$$f(x) < Mg(x)$$f(x) \not\in O(g(x))$

$Mf(x)$$g(x)$, ten sam pomysł będzie miał zastosowanie do $g(x) = \log(x)$

Oto para funkcji monotonicznych , które nie są asymptotycznie porównywalne. Jest to istotne, ponieważ większość złożoności powstających w praktyce jest w rzeczywistości monotoniczna.

Here, $\Gamma$ is the gamma function. The second function is specially constructed to be very similar to the factorial, just "sampled" at slightly offset points in the gamma function. The functions cross each other periodically in such a way that neither is asymptotically bound by the other.

Let $\mathcal{L}$ be the class of functions obtained from the identity function and constants using the following operations: addition, subtraction, multiplication, division, logarithm and exponential. For example, $\exp(2\sqrt{\log x + \log\log x})/x^2$. Hardy proved that for every two functions $f,g \in \mathcal{L}$ which are positive and tend to infinity, one of the following is true: $f = o(g)$, $f = \omega(g)$, $f/g$ tends to a constant. See page 18 of his book "Orders of infinity".

The upshot is that any two "simple" functions occurring in the analysis of algorithm are comparable. Here "simple" means that there is no definition by cases (other than finitely many base cases), and no surprising functions appear, such as the inverse Ackermann function which sometimes figures in running times.