Comment déterminer si la complexité de temps est O (m + n) ou O (Math.max (m, n))

Question

Je passais ce code mais j'ai du mal à comprendre comment c'est O (m + n) au lieu de O (Math.max (m, n)). Ou est O (m + n) sous O (Math.max (m, n)) de toute façon?

int i = 0, j = 0, res = 0; 
    while (i < houses.length) { 
     while (j < heaters.length - 1 
      && Math.abs(heaters[j + 1] - houses[i]) <= Math.abs(heaters[j] - houses[i])) { 
      j++; 
     } 
     res = Math.max(res, Math.abs(heaters[j] - houses[i])); 
     i++; 
    } 

Il existe un exemple sur CTCI où la fonction renvoie un tableau de taille n. Il dit que la complexité de log (n) due aux appels de pile est réduite lorsque l'on calcule un grand O depuis n> logn, ce qui donne O (n) globalement. O (n + logn) n'est pas mentionné dans cet exemple (4.4 pour les curieux).

Une explication serait appréciée!

Answer 1

Comme vous l'aurez deviné déjà, sous le Big-O-Notation est à la fois la même.

Les deux fonctions, m + n et max(m, n), sont des éléments de l'ensemble O(m + n) = O(max(m, n).

---

Faisons le calcul:

m + n <= max(m, n) + max(m, n) = 2 * max(m, n) et aussi
max(m, n) <= m + n aussi longtemps que min(m, n) >= 0 (mais m, n >= 0 déjà)

Ainsi, les deux fonctions sont limitées par l'autre fonction (plus un facteur constant) , par conséquent O(m + n) ou O(max(m, n)), les ensembles sont égaux.

Voici la définition formelle (1 dimensions) (à partir Wikipedia):

---

Intuitivement il a également est logique que les deux fonctions que signifient croissance linéaire dans les deux variables et rien de plus.

---

[...] résultant en O (n) ensemble. O (n + logn) n'est pas mentionné [...]

Je ne sais pas si c'est une question. Il suffit de noter que les deux ensembles sont à nouveau les mêmes que n <= n + log(n) et n + log(n) <= n + n = 2 * n, linéaire en n.