Ik ben nieuw op de computerwetenschappen en is net begonnen met pseudocodes en ik heb enkele vragen. Het is mijn derde week in het semester en de meerderheid is zelfstudie. Ik heb wat vragen:
Wat is het verschil van een O (N ^ 2) met een O (n) algoritme?
– op dezelfde manier, wat is o (n log n)?
– en ω (n ^ 2)?
Tot nu toe heb ik geschreven:
horner = 0;
for( i = n; i >= 0; i −− )
horner = x * horner + a[i];
maar ontdekt dat het o (n) is. Hoe transformeer ik het?
Wat is de runtime?
– Ik weet dat opdracht op de eerste regel 1 bediening
is
En hoe ziet het eruit in een echte, zeg C #, algoritme?
Antwoord 1, Autoriteit 100%
Waar u naar vraagt, is een onderwerp in de computerwetenschap die bekend staat als algoritme-complexiteitsanalyse. Het is een heel belangrijk onderwerp om te overwegen bij het schrijven van algoritmen of oplossingen, in uw programma’s, omdat het betrekking heeft op run-time, of hoe snel uw berekeningen zullen worden uitgevoerd.
Big-OH, of O (n) heeft betrekking op de bovenste runtime voor een algoritme om te rennen. In dit geval, o (n) betekent voor N-elementen, zullen er alle n-elementen zijn die worden overwogen voor de algoritmen-berekening om te voltooien of lineair. Het bereik voor deze Big-Oh-complexiteit is van constante tijd, O (1), naar boven O (N ^ n) voor echt grote en zeer langzame berekeningen. Overweeg ook vergelijkingen zoals het volgende:
y=10n+1
y=5n+10
Deze zijn beide o (n) complexiteit omdat het aantal elementen groeit, groeit de vergelijking groter en groter vanwege het. We verwaarlozen de constanten omdat de vergelijking groter en snel zal worden vanwege de variabele, in plaats van te wijten aan de constante waarden die nooit veranderen.
Dat, met vergelijking als het volgende:
y=10n^2+5n+5
De complexiteit zal O(n^2) zijn, omdat 10n^2 het grootste groeiende element is dat ertoe bijdraagt dat de vergelijking sneller groeit. We laten de constanten vallen en beschouwen de grootste groeiende componenten voor vergelijkingen om de complexiteit te evalueren.
Voor Big-Omega-complexiteit beschouwen we dit als de ondergrens voor Algoritme Complexiteitsanalyse. Een algoritme kan bijvoorbeeld zo snel werken als Omega(n) (best case), maar net zo lang duren als O(n^2) (worst case). Dit is gebruikelijk bij de analyse van sorteeralgoritmen of zoekalgoritmen.
In sommige gevallen willen we programma’s schrijven met algoritmen die om optimalisatieredenen efficiënt en sneller zijn, vooral als we een sneller programma willen voor snellere oplossingen of snellere uitvoeringstijden.
Het codevoorbeeld dat je hebt gegeven is O(n) omdat het een for-lus gebruikt om over n-elementen te itereren. Overweeg een dubbele for-lus, waarbij er een tweede lus is binnen uw huidige for-lus. Dit is O(n^2) vanwege iteratie over, in het ergste geval, n*n elementen.
Java pseudo-code voor een O(n^2) runtime die een lege matrix initialiseert:
int result[n][m];
for(int i=0; i<n; ++i){
for(int j=0; j<m; ++j){
result[i][j] = 0;
}
}
Let op, het gebruikt twee lussen en induceert daarom een O(n^2) runtime.
Hier is een grafiek om te laten zien hoe vergelijkingen in de loop van de tijd groeien: (en hoe snel ze groeien)
Antwoord 2, autoriteit 23%
O(n)geeft het aantal iteraties, berekeningen of stappenaan dat hoogstens (in het slechtste geval)nodig is om het algoritme te bereiken zijn eindtoestand, waarbij nde objecten zijn die aan het begin van het algoritme worden gegeven.
Stel dat je een array van 5 elementen hebt en een sorteeralgoritme met O(n^2) complexiteit. U weet dat als u de sortering op de array toepast, deze maximaal 5^2=25 stappen nodig heeft om de eindtoestand te bereiken.
Lees ook: Wat is het verschil tussen O, Ω en Θ?