stratosfe
01-07-2008, 18:07
Salve avrei da fare alcune domande sulla complessità in genere e su quella di alcuni algortimi e strutture dati.. 1) quando faccio la ricerca in un array disordinato la complessità intrinseca è omega(log n) ?
2) Se per una funzione f ho trovato che la complessità è O(n) allora posso dire che è anche omega(n^2) ?
3) Se ho un problema con complessità omega(n^2) allora posso dire che esiste almeno un algoritmo risolutore che ha complessità omega(n) ?
4) Quando faccio un inserimento in un heap, il costo è teta(n) ?
5) Se ho trovato la funzione 2 n log n^2 allora la complessità è O(n log n)?
Se qualcuno può dirmi se le mie ipotesi sono esatte... Grazie...
2) Se per una funzione f ho trovato che la complessità è O(n) allora posso dire che è anche omega(n^2) ?
3) Se ho un problema con complessità omega(n^2) allora posso dire che esiste almeno un algoritmo risolutore che ha complessità omega(n) ?
4) Quando faccio un inserimento in un heap, il costo è teta(n) ?
5) Se ho trovato la funzione 2 n log n^2 allora la complessità è O(n log n)?
Se qualcuno può dirmi se le mie ipotesi sono esatte... Grazie...