Notazione O grande e Omega

5 Risposte

• M

  maffo95

  Utente Attivo

  Iscritto da

  mar, 2015

  Messaggi:

  153

  Re: Notazione O grande e Omega

  07 mag 2017, 18:09

  Cerco di essere il più chiaro e concreto possibile...la O (=ordine) praticamente indica che la funzione a cui si riferisce ha un limite superiore per esempio un ciclo while(c<=n) è O(n) perchè la funzione potrebbe finire o con un c<n o con c=n ma mai con un c>n (quindi è utilizzata sempre per funzioni che possono anche non arrivare mai ad n pensa ad una ricerca in un array, se è al primo posto l'elemento che cerchi finisci subito altrimenti continua).
  L'Omega è essenzialmente la solita cosa solo che la funzione con questa complessità copre sempre "tutto lo spazio" prima (e compreso) il limite superiore scritto tra parentesi. Un esempio è la stampa degli elementi di un array, il programma deve prendere in considerazione tutti i numeri dell'array per poterli stampare a video.
  
  Spero tu abbia capito ho cercato di essere il più concreto possibile e di fartelo capire più che altro per la materia che stai affrontando ora (un matematico avrebbe tanto da ridire su la mia spiegazione ma siamo programmatori siamo più concreti noi ahahah )
• R

  rairana

  Utente Attivo

  Iscritto da

  set, 2015

  Messaggi:

  65

  Re: Notazione O grande e Omega

  07 mag 2017, 19:41

  maffo95 ha scritto:

  ---

  Cerco di essere il più chiaro e concreto possibile...la O (=ordine) praticamente indica che la funzione a cui si riferisce ha un limite superiore per esempio un ciclo while(c<=n) è O(n) perchè la funzione potrebbe finire o con un c<n o con c=n ma mai con un c>n (quindi è utilizzata sempre per funzioni che possono anche non arrivare mai ad n pensa ad una ricerca in un array, se è al primo posto l'elemento che cerchi finisci subito altrimenti continua).
  L'Omega è essenzialmente la solita cosa solo che la funzione con questa complessità copre sempre "tutto lo spazio" prima (e compreso) il limite superiore scritto tra parentesi. Un esempio è la stampa degli elementi di un array, il programma deve prendere in considerazione tutti i numeri dell'array per poterli stampare a video.
  
  Spero tu abbia capito ho cercato di essere il più concreto possibile e di fartelo capire più che altro per la materia che stai affrontando ora (un matematico avrebbe tanto da ridire su la mia spiegazione ma siamo programmatori siamo più concreti noi ahahah )

  La tua spiegazione, naturalmente per il corso che sto facendo è stata impeccabile, ma potresti dirmi il caso peggiore, migliore e medio come sono collegati con O grande e l'Omega?
• M

  maffo95

  Utente Attivo

  Iscritto da

  mar, 2015

  Messaggi:

  153

  Re: Notazione O grande e Omega

  07 mag 2017, 19:52

  Prima ti dico che per l'omega mi sono sbagliato ahahah quello che intendevo io è la O con tipo un ondina dentro (mi sembra si chiama O-tilde ma non ne sono certo)...
  L'Omega è rappresentabile come il limite inferiore della funzione ovvero i passi minimi che servono per risolvere il problema per esempio se ricordo bene il limite inferiore dell'ordinamento è Omega(n*log(n)) calcolabile attraverso l'albero di decisione con il metodo Divide Et Impera quindi vuol dire che il programma che devi creare non può risolvere il problema senza aver fatto almeno n*log(n) passi (Poi magari ti farà vedere il counting sort che risolve il problema in tempo lineare ma quello non conta è un "trucchetto" informatico per così dire).
  Quindi ricapitolando:
  CASO PEGGIORE = limite superiore (O);
  CASO MIGLIORE = limite inferiore (Omega);
  CASO MEDIO = tutto il tempo che intercorre tra lim. inf. e lim. sup. (la O con dentro l'ondina).
• R

  rairana

  Utente Attivo

  Iscritto da

  set, 2015

  Messaggi:

  65

  Re: Notazione O grande e Omega

  07 mag 2017, 20:40

  maffo95 ha scritto:

  ---

  Prima ti dico che per l'omega mi sono sbagliato ahahah quello che intendevo io è la O con tipo un ondina dentro (mi sembra si chiama O-tilde ma non ne sono certo)...
  L'Omega è rappresentabile come il limite inferiore della funzione ovvero i passi minimi che servono per risolvere il problema per esempio se ricordo bene il limite inferiore dell'ordinamento è Omega(n*log(n)) calcolabile attraverso l'albero di decisione con il metodo Divide Et Impera quindi vuol dire che il programma che devi creare non può risolvere il problema senza aver fatto almeno n*log(n) passi (Poi magari ti farà vedere il counting sort che risolve il problema in tempo lineare ma quello non conta è un "trucchetto" informatico per così dire).
  Quindi ricapitolando:
  CASO PEGGIORE = limite superiore (O);
  CASO MIGLIORE = limite inferiore (Omega);
  CASO MEDIO = tutto il tempo che intercorre tra lim. inf. e lim. sup. (la O con dentro l'ondina).

  
  Grazie mille, adesso ho capito anche se in modo superficiale il significato...
• 

  trafalgar

  Pochi posts

  Iscritto da

  apr, 2017

  Messaggi:

  23

  Re: Notazione O grande e Omega

  07 mag 2017, 23:22

  Ciao,anche io sto studiando la complessità computazionale.
  
  Da quello che ci ha spiegato il prof esistono tre notazioni:la prima è omega,la seconda è O grande (come l'hai chiamata) se
  non sbaglio si chiama omicron,ed infine theta o O-tile come l'ha chiamata maffo95,ma non fidarti dei nomi
  che potrebbero essere sbagliate.
  

  maffo95 ha scritto:

  ---

  quello che intendevo io è la O con tipo un ondina dentro (mi sembra si chiama O-tilde ma non ne sono certo)..

  Comunque devi pensare in termini matematici,ossia immaginare di avere una funzione. Questa nel caso di theta sarà compresa tra altre due funzioni
  mentre negli altri due casi esisterà una funzione che da un certò valore in poi risulterà sempre maggiore o minore della funzione data.
  
  Inoltre ogni algoritmo può essere associato alla complessità di altri, ad esempio n logn (pensa al merge sort), log n, n al quadrato, n al cubo e cosi via...
  Il nostro prof ci fa "contare le istruzioni",ossia ipotizza un costo unitario( cioè di uno) per singola istruzione e poi sommiamo i vari costi.