Credo che dobbiamo usare una variante del teorema del master ... qualcuno può suggerirmi come trovare la complessità di tale equazione che non si adatta direttamente al teorema di Masters.
Credo che dobbiamo usare una variante del teorema del master ... qualcuno può suggerirmi come trovare la complessità di tale equazione che non si adatta direttamente al teorema di Masters.
Per prima cosa ho messo parentesi attorno alle espressioni per chiarire qual è il lato destro in realtà. Una volta chiaro che è (n ^ 2.93) * ((log n) ^ 93) = o (n ^ 3) la soluzione è facile, ma piuttosto inutile: se log n è il logaritmo naturale, quindi per n ≥ 8 o così nessun computer al mondo risolverà mai il problema. Se log n è logaritmo di base 10, lo stesso vale per n = 100.
Se lo si traccia e si conclude che (n ^ 2.93) * ((log n) ^ 93) è sempre maggiore di n ^ 3: Se log è il logaritmo naturale, allora n ^ 3 è maggiore quando x è intorno a 10 ^ 5445.
PS. codesInChaos apparentemente non è molto esperto con l'uso di little-o. È molto comune usare = e non "elemento di" con notazione big-O / little-o, e tutto ciò che cresce più lentamente di n ^ 3 è in effetti o (n ^ 3).
Leggi altre domande sui tag algorithms algorithm-analysis