Si f (n) es O (g (n)) yf (n) es O (h (n)), ¿significa que g (n) es O (h (n))?

f (n) = O (g (n)) tipo de lecturas f (n) <= k * g (n).

Precisamente hablando

f (n) = O (g (n)) <=> Existen N, k> 0 (para todos n> = N, f (n) <= k * g (n)).

En inglés, “for all n> = N” es solo una forma rigurosa de decir “para n lo suficientemente grande” mientras que k> 0 existe para eliminar múltiplos constantes.

Entonces puede leer “f (n) es O (g (n)) yf (n) es O (h (n))” como “f (n) es ‘más pequeño o igual a’ que ambos g (n) y h (n) ”, pero eso no descarta el caso de que g (n) sea ‘más grande’ que h (n).

Esto es similar a cómo a <= by a <= c no le permite concluir b <= c.

Si necesita un contraejemplo,

let f (n) = 1. g (n) = n !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!, h (n) = n.

Claramente 1 <= ny 1 <= n !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!, pero g (n) definitivamente no está limitado asintóticamente por encima de una función lineal, o cualquier aspecto razonable.

No. A menos que use límites estrechos para las complejidades asintóticas. Un simple ejemplo de contador es:

[matemáticas] n \ en O (n ^ {10}) [/ matemáticas]

[matemáticas] n \ en O (n ^ 2) [/ matemáticas]

pero claramente

[matemáticas] n ^ {10} \ not \ en O (n ^ 2) [/ matemáticas]

Utilice [matemática] f \ en notación O (g) [/ matemática] en lugar de =. Es terriblemente confuso. El resumen es, O () no es una notación de equivalencia, [math] \ Theta [/ math] es. De hecho, lea esto.

[1304.5617] Otra notación asintótica: “Casi”

O (g (n)) es un límite superior, no una clase de equivalencia. Una clase de equivalencia es si f (n) es tanto O (g (n)) como Omega (g (n)). Llamemos a esto Theta (g (n)). Si f (n) es Theta (g (n)) y Theta (h (n)), entonces también gyh son equivalentes. Pero con O (), si a <= by a <= c, ¿resulta que b <= c?