Quote:
|
Originariamente inviato da Brazorv
secondo me stai facendo un pò di confusione. Tu stai parlando di costanti, ma in questo caso n ed m non sono costanti, ma sono le variabili che definiscono la complessità dell'algoritmo, per cui ha senso scrivere O(n+m).
|
non ci siamo capiti, cerco di essere più chiaro...
- se n è minore di m (ovvero n~ o(m)) allora non ha senso sommare ad m che è di almeno un ordine di grandezza superiore un numero n di grandezza inferiore. si deduce che la complesità in questo caso è pari a O(m)
- se n è magigore di m (ovvero m~ o(n)) vale il discorso contrario e la complessità è O(n)
- se n e m sono dello stesso ordine di grandezza allora dire O(n+m) significherebbe dire O(2*n) oppure O(2*m) che secondo queste notazioni equivarrebbe a dire O(n) oppure O(m)
spero di essere stato più chiaro...
EDIT
se n e m sono dello stesso ordine di grandezza allora vorrebbe dire che O(n+m) è assimilabile a O(2*n) ma anche a O(10000000000*n) - con la stessa cosa che vale anche per m. quindi più in generale O(n+m) ~ O(k*n) ~ O(k*m) con k costante.